双链表
链表中的每个节点即指向前面一个节点，也指向后面一个节点，就像丢手绢游戏一样，每个人都手拉手 。简单来说，双向链表其实和单链表类似的，只是在定义存储结构时多了一个指向前驱结点，删除时只要更新当前的结点指向的前驱结点的下一个结点为当前结点的下一个结点即可，
头插法
这里看图就行了
这里图写错了，我这种应该不是第一次插入的场景，第一次插入头和尾结点直接指向node，当第二次的时候
|
1 2 3 |
node.next = this.head;//直接引导，让node2指向node this.head.prev=node;//回溯，使得node回向node2，单链表时候这个可以去掉 this.head=node;//为下次做铺垫 |
尾插法
尾插法这里图也画错了，
|
1 2 3 |
this.tail.next = node;//这里直接node.next=node2 node.prev=this.tail;//node2.prev = node this.tail=node;//为下次做铺垫 |
不得不说，这个java的双链表比c++要简单多了
代码
|
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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 |
package zy_2021_12.doubleLink; class Node{ public int data;//数据 public Node next;//后继信息 public Node prev;//前驱信息 //提供构造方法 public Node(int data){ this.data = data; } } public class DoubleLinkedList { public Node head; //表示双向链表的头 public Node tail; //表示当前双向链表的尾 //1.打印链表 //记住，尾插法遍历值，也是从头结点开始，如果是单链表，那么尾插法需要一个头结点 public void print(){ Node cur = this.head; while(cur != null){ System.out.print(cur.data+" "); cur = cur.next; } System.out.println(); } //2.头插法 public void addFirst(int data){ Node node = new Node(data); //第一次插入 if(this.head == null){ this.head = node; this.tail = node; } //不是第一次插入 else{ node.next = this.head; this.head.prev = node; this.head = node; } } //3.尾插法 public void addLast(int data){ Node node = new Node(data); //第一次插入 if(this.head == null){ this.head = node; this.tail = node; } //不是第一次插入 else{ this.tail.next = node; node.prev = this.tail; this.tail = node; } } private void checkIndex(int index){ if(index < 0 || index > len()){ throw new RuntimeException("index不合法！！"); } } private Node searchIndex(int index){ Node cur = this.head; while(index != 0) { cur = cur.next; index--; } return cur; } //4.任意位置插入，第一个数据节点为0号下标 public void addIndex(int index,int data){ checkIndex(index); if(index == 0){ addFirst(data); return; } if(index == len()){ addLast(data); return; } Node node = new Node(data); Node cur = searchIndex(index); node.next = cur; node.prev = cur.prev; cur.prev.next = node; cur.prev = node; } //5.查找链表中是否包含关键字 key public boolean containKey(int key){ Node cur = this.head; while(cur != null){ if(cur.data == key){ return true; } cur = cur.next; } return false; } //6.删除第一次出现关键字为 key 的节点 public void deleteKey(int key){ Node cur = this.head; while(cur != null){ if(cur.data == key){ //头节点 if(cur == this.head){ this.head = this.head.next; this.head.prev = null; } //中间节点 else{ cur.prev.next = cur.next; if(cur.next != null){ cur.next.prev = cur.prev; } //删除的是尾节点,只需要移动tail else{ this.tail = cur.prev; } } } cur = cur.next; } } //7.删除所有关键字为 key 的节点 public void deleteAllKey(int key){ Node cur = this.head; while(cur != null){ if(cur.data == key){ //头节点 if(cur == this.head){ this.head = this.head.next; if(this.head != null){ this.head.prev = null; } } //中间节点 else{ cur.prev.next = cur.next; if(cur.next != null){ cur.next.prev = cur.prev; } //删除的是尾节点,只需要移动tail else{ this.tail = cur.prev; } } } cur = cur.next; } } //8.链表长度 public int len(){ int count = 0; Node cur = this.head; while(cur != null){ count++; cur = cur.next; } return count; } //9.链表清空 public void clear(){ //一个一个节点进行释放 while(this.head != null){ Node cur = this.head.next; this.head.prev = null; this.head.next = null; this.head = cur; } this.tail = null; } //根据index移除数据 public int remove(int index){ int data; checkIndex(index); Node cur = this.head; //找到index+1个结点 while(index-1 != 1) { cur = cur.next; index--; } if(cur==null) return 0;//表示index越界 else{ Node tmp = cur.next;//tmp代表要删除的结点 if(tmp==null) return 0; data = tmp.data; cur.next = tmp.next; //java中不需要释放对象，由jvm虚拟机管理 } return data; } } |
主main测试
|
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 |
package zy_2021_12.doubleLink; import zy_2021_12.doubleLink.zy.DoubleLinkedList2; import java.util.Scanner; /** * @date 2021/11/30 9:01 */ public class Main { public static void main(String[] args) { DoubleLinkedList2 doubleLinkedList = new DoubleLinkedList2(); Scanner sc = new Scanner(System.in); System.out.println("头插法插入值1，2，3"); System.out.println(doubleLinkedList.insertFirst(1)); System.out.println(doubleLinkedList.insertFirst(2)); System.out.println(doubleLinkedList.insertFirst(3)); System.out.println("插入后的结果:"); doubleLinkedList.print(); System.out.println("尾插法插入值4，5，6"); System.out.println(doubleLinkedList.insertLast(4)); System.out.println(doubleLinkedList.insertLast(5)); System.out.println(doubleLinkedList.insertLast(6)); System.out.println("插入后的结果:"); doubleLinkedList.print(); System.out.println("请输入你要插入的结点之后的位置(insertAfter)和要插入的数据"); doubleLinkedList.insertAfter(sc.nextInt(),sc.nextInt()); System.out.println("插入后的结果："); doubleLinkedList.print(); System.out.println("请输入你要插入的结点之前的位置(insertBefore)和要插入的数据"); doubleLinkedList.inserBefore(sc.nextInt(),sc.nextInt()); System.out.println("插入后的结果："); doubleLinkedList.print(); System.out.println("请输入你要删除的结点的位置(remove)"); int data = doubleLinkedList.remove(sc.nextInt()); System.out.println("被删除的数据："+data); System.out.println("删除后结果"); doubleLinkedList.print(); } } |
总结
这里我有个概念混淆了，双链表是双链表是结点1和2能相互指向的链表，和头插入和尾插入没关系，但是双链表却是需要两个结点，一个从头遍历，一个从尾遍历嘛