本篇文章为你整理了单向链表的介绍和实现思路(单向链表是什么)的详细内容,包含有单向链表结构图 单向链表是什么 单向链表的定义 单向链表的优点和缺点 单向链表的介绍和实现思路,希望能帮助你了解 单向链表的介绍和实现思路。
链表在内存中的存储
特点
链表是以节点的方式来存储,是链式存储
每个节点包含 data 域 和 next 域。next域用来指向下一个节点
链表的各个节点不一定是连续存储的
链表分带头节点的链表和没有头节点的链表,根据实际的需求来确定
带头结点的逻辑示意图
创建(添加)
先创建一个Head头节点,表示单链表的头
后面我们每添加一个节点,就放在链表的最后
遍历
通过一个辅助变量,来遍历整个链表
有序插入
先遍历链表,找到应该插入的位置
要插入的节点的next指向插入位置的后一个节点
插入位置的前一个节点的next指向要插入节点
插入前要判断是否在队尾插入
翻转链表
创建一个新的头结点,作为新链表的头
从头遍历旧链表,将遍历到的节点插入新链表的头结点之后
注意需要用到两个暂存节点
一个用来保存正在遍历的节点
一个用来保存正在遍历节点的下一个节点
逆序打印
遍历链表,将遍历到的节点入栈
遍历完后,进行出栈操作,同时打印出栈元素
代码
public class Demo1 {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.traverseNode();
System.out.println();
//创建学生节点,并插入链表
StudentNode student1 = new StudentNode(1, "Nyima");
StudentNode student3 = new StudentNode(3, "Lulu");
linkedList.addNode(student1);
linkedList.addNode(student3);
linkedList.traverseNode();
System.out.println();
//按id大小插入
System.out.println("有序插入");
StudentNode student2 = new StudentNode(0, "Wenwen");
linkedList.addByOrder(student2);
linkedList.traverseNode();
System.out.println();
//按id修改学生信息
System.out.println("修改学生信息");
student2 = new StudentNode(1, "Hulu");
linkedList.changeNode(student2);
linkedList.traverseNode();
System.out.println();
//根据id删除学生信息
System.out.println("删除学生信息");
student2 = new StudentNode(1, "Hulu");
linkedList.deleteNode(student2);
linkedList.traverseNode();
System.out.println();
//获得倒数第几个节点
System.out.println("获得倒数节点");
System.out.println(linkedList.getStuByRec(2));
System.out.println();
//翻转链表
System.out.println("翻转链表");
LinkedList newLinkedList = linkedList.reverseList();
newLinkedList.traverseNode();
System.out.println();
//倒叙遍历链表
System.out.println("倒序遍历链表");
newLinkedList.reverseTraverse();
* 创建链表
class LinkedList {
//头节点,防止被修改,设置为私有的
private StudentNode head = new StudentNode(0, "");
* 添加节点
* @param node 要添加的节点
public void addNode(StudentNode node) {
//因为头节点不能被修改,所以创建一个辅助节点
StudentNode temp = head;
//找到最后一个节点
while (true) {
//temp是尾节点就停止循环
if(temp.next == null) {
break;
//不是尾结点就向后移动
temp = temp.next;
//现在temp是尾节点了,再次插入
temp.next = node;
* 遍历链表
public void traverseNode() {
System.out.println("开始遍历链表");
if(head.next == null) {
System.out.println("链表为空");
//创建辅助节点
StudentNode temp = head.next;
while(true) {
//遍历完成就停止循环
if(temp == null) {
break;
System.out.println(temp);
temp = temp.next;
* 按id顺序插入节点
* @param node
public void addByOrder(StudentNode node) {
//如果没有首节点,就直接插入
if(head.next == null) {
head.next = node;
return;
//辅助节点,用于找到插入位置和插入操作
StudentNode temp = head;
//节点的下一个节点存在,且它的id小于要插入节点的id,就继续下移
while (temp.next!=null temp.next.id node.id) {
temp = temp.next;
//如果temp的下一个节点存在,则执行该操作
//且插入操作,顺序不能换
if(temp.next != null) {
node.next = temp.next;
temp.next = node;
* 根据id来修改节点信息
* @param node 修改信息的节点
public void changeNode(StudentNode node) {
if(head == null) {
System.out.println("链表为空,请先加入该学生信息");
return;
StudentNode temp = head;
//遍历链表,找到要修改的节点
while (temp.next!= null temp.id != node.id) {
temp = temp.next;
//如果temp已经是最后一个节点,判断id是否相等
if(temp.id != node.id) {
System.out.println("未找到该学生的信息,请先创建该学生的信息");
return;
//修改学生信息
temp.name = node.name;
* 根据id删除节点
* @param node 要删除的节点
public void deleteNode(StudentNode node) {
if(head.next == null) {
System.out.println("链表为空");
return;
StudentNode temp = head.next;
//遍历链表,找到要删除的节点
if(temp.next!=null temp.next.id!=node.id) {
temp = temp.next;
//判断最后一个节点的是否要删除的节点
if(temp.next.id != node.id) {
System.out.println("请先插入该学生信息");
return;
//删除该节点
temp.next = temp.next.next;
* 得到倒数的节点
* @param index 倒数第几个数
* @return
public StudentNode getStuByRec(int index) {
if(head.next == null) {
System.out.println("链表为空!");
StudentNode temp = head.next;
//用户记录链表长度,因为head.next不为空,此时已经有一个节点了
//所以length初始化为1
int length = 1;
while(temp.next != null) {
temp = temp.next;
length++;
if(length index) {
throw new RuntimeException("链表越界");
temp = head.next;
for(int i = 0; i length-index; i++) {
temp = temp.next;
return temp;
* 翻转链表
* @return 反转后的链表
public LinkedList reverseList() {
//链表为空或者只有一个节点,无需翻转
if(head.next == null head.next.next == null) {
System.out.println("无需翻转");
LinkedList newLinkedList = new LinkedList();
//给新链表创建新的头结点
newLinkedList.head = new StudentNode(0, "");
//用于保存正在遍历的节点
StudentNode temp = head.next;
//用于保存正在遍历节点的下一个节点
StudentNode nextNode = temp.next;
while(true) {
//插入新链表
temp.next = newLinkedList.head.next;
newLinkedList.head.next = temp;
//移动到下一个节点
temp = nextNode;
nextNode = nextNode.next;
if(temp.next == null) {
//插入最后一个节点
temp.next = newLinkedList.head.next;
newLinkedList.head.next = temp;
head.next = null;
return newLinkedList;
public void reverseTraverse() {
if(head == null) {
System.out.println("链表为空");
StudentNode temp = head.next;
//创建栈,用于存放遍历到的节点
Stack StudentNode stack = new Stack ();
while(temp != null) {
stack.push(temp);
temp = temp.next;
while (!stack.isEmpty()) {
System.out.println(stack.pop());
* 定义节点
class StudentNode {
int id;
String name;
//用于保存下一个节点的地址
StudentNode next;
public StudentNode(int id, String name) {
this.id = id;
this.name = name;
@Override
public String toString() {
return "StudentNode{" +
"id=" + id +
", name=" + name + \ +
};
本文来自,作者:腹白,转载请注明原文链接:https:///wyh518/
以上就是单向链表的介绍和实现思路(单向链表是什么)的详细内容,想要了解更多 单向链表的介绍和实现思路的内容,请持续关注盛行IT软件开发工作室。
郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。