单链表：
每个数据是以节点的形式存在的
每个节点分为数据域和指针域
数据域中保存该节点的数据
指针域中保存指向下一个节点的指针
实现思路：
节点类SingleNode中保存数据和指向下一个节点的指针
单链表类SingleLinkedList中保存链表的头节点，实现相关链表方法
对于链表方法，涉及到位置查找，如在指定位置增加、删除节点，需要使用一个临时变量temp从头节点开始遍历，直至找到对应的位置。
对于节点的增加删除，只需要修改相关结点的指针指向即可
代码实现：
节点类SingleNode：
|
1 2 3 4 5 6 7 8 9 10 11 |
public class SingleNode { public int data; public SingleNode next; public SingleNode( int data) { this .data = data; } @Override public String toString() { return "SingleNode{" + "data=" + data + '}' ; } } |
单链表类SingleLinkedList ：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
public class SingleLinkedList { private SingleNode head = new SingleNode( 0 ); //获取头结点 public SingleNode getHead(){ return head; } //添加节点 public void add(SingleNode singleNode) { SingleNode temp = head; //找到链表最后一个节点 while (temp.next != null ) { temp = temp.next; } temp.next = singleNode; } //按顺序添加节点 public void addByOrder(SingleNode singleNode) { SingleNode temp = head; while ( true ) { if (temp.next == null ) { //已经遍历到链表最后了 break ; } else if (temp.next.data > singleNode.data) { //找到应插入的位置 break ; } temp = temp.next; } singleNode.next = temp.next; temp.next = singleNode; } //删除节点 public void delete( int data) { SingleNode temp = head; boolean flag = false ; //标志是否找到待删除节点的前一个节点 while ( true ) { if (temp.next == null ) { //已经遍历到链表最后了 break ; } else if (temp.next.data == data) { //找到待删除节点的前一个节点 flag = true ; break ; } temp = temp.next; } if (flag) { temp.next = temp.next.next; } else { System.out.println( "要删除的节点不存在" ); } } //输出链表 public void show() { //判断链表是否为空 if (head.next == null ) { System.out.println( "链表为空" ); return ; } SingleNode temp = head.next; while (temp != null ) { System.out.println(temp); temp = temp.next; } } } |
双向链表：
每个节点中除了保存了指向后一个节点的指针外，还保存了指向前一个节点的指针
实现思路：
相关方法实现与单链表类似，不同点在于需要增加对指向前一个节点的指针的更改
代码实现：
节点类DoubleNode：
|
1 2 3 4 5 6 7 8 9 10 11 12 |
public class DoubleNode { public int data; public DoubleNode next; public DoubleNode pre; public DoubleNode( int data) { this .data = data; } @Override public String toString() { return "DoubleNode{" + "data=" + data + '}' ; } } |
双向链表类DoubleLinkedList：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
public class DoubleLinkedList { public DoubleNode head = new DoubleNode( 0 ); //获取头结点 public DoubleNode getHead() { return head; } //添加节点 public void add(DoubleNode doubleNode) { DoubleNode temp = head; //找到链表最后一个节点 while (temp.next != null ) { temp = temp.next; } temp.next = doubleNode; doubleNode.pre = temp; } //删除节点 public void delete( int data) { DoubleNode temp = head.next; boolean flag = false ; //标志是否找到待删除节点的前一个节点 while ( true ) { if (temp == null ) { //已经遍历到链表最后了 break ; } else if (temp.data == data) { //找到待删除节点 flag = true ; break ; } temp = temp.next; } if (flag) { temp.pre.next = temp.next; if (temp.next != null ) { //若删除节点不为最后一个节点 temp.next.pre = temp.pre; } } else { System.out.println( "要删除的节点不存在" ); } } //输出链表 public void show() { //判断链表是否为空 if (head.next == null ) { System.out.println( "链表为空" ); return ; } DoubleNode temp = head.next; while (temp != null ) { System.out.println(temp); temp = temp.next; } } } |
总结
本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注的更多内容！
原文链接：https://blog.csdn.net/qq_25274377/article/details/119246506
查看更多关于java数据结构基础:单链表与双向链表的详细内容...