【java基础】浅谈链表结构

链表的概念

链表是一种递归的数据结构，它或者为空（null），或者是指向一个结点（node）的引用，该节点还有一个元素和一个指向另一条链表的引用。

在Java中LinkedList就是一个典型的(单向)链表结构（它的一个实例域保存了指向链表中第一个结点的引用）

class LinkedList<Item>{ private Node first; //当前节点 private class Node{ Item data; Node next; //下一节点 } · · · · · · }

单向链表

node包含指向后一个节点的引用

双向链表

每个node不仅包含指向下后一个结点的引用，还包含着指向前一个结点的引用。

链表的优点

链表支持插入和删除这两种操作，并且删除/插入链表头部/尾部结点的时间复杂度通常都是常数级别 [ O(1) ]可以动态改变大小。

链表的缺点

不支持高效的random access（随机访问）。

由于其链式存储的特性，链表不具备良好的空间局部性，也就是说，链表是一种缓存不友好的数据结构。

链表的实现

单向链表

插入节点

public Item delete() { if (first != null) { Item item = first.item; first = first.next; return item; } else { throw new NullPointerException("There's no Node in the linked list."); } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 双向链表 双向链表相比与单链表的优势在于它同时支持高效的正向及反向遍历，并且可以方便的在链表尾部删除结点 Java实现 public class DoubleLinkedList<Item> { private Node first; private Node last; private int itemCount; private class Node { Node prev; Node next; Item item; } public void addFirst(Item item) { Node oldFirst = first; first = new Node(); first.item = item; first.next = oldFirst; if (oldFirst != null) { oldFirst.prev = first; } if (itemCount == 0) { last = first; } itemCount++; } public void addLast(Item item) { Node oldLast = last; last = new Node(); last.item = item; last.prev = oldLast; if (oldLast != null) { oldLast.next = last; } if (itemCount == 0) { first = last; } itemCount++; } public Item delFirst() { if (first == null) { throw new NullPointerException("No node in linked list."); } Item result = first.item; first = first.next; if (first != null) { first.prev = null; } if (itemCount == 1) { last = null; } itemCount--; return result; } public Item delLast() { if (last == null) { throw new NullPointerException("No node in linked list."); } Item result = last.item; last = last.prev; if (last != null) { last.next = null; } if (itemCount == 1) { first = null; } itemCount--; return result; } public void addBefore(Item targetItem, Item item) { //从头开始遍历寻找目标节点 Node target = first; if (target == null) { throw new NullPointerException("No node in linked list"); } while (target != null && target.item != targetItem) { //继续向后寻找目标节点 target = target.next; } if (target == null) { throw new NullPointerException("Can't find target node."); } //现在target为指向目标结点的引用 if (target.prev == null) { //此时相当于在表头插入结点 addFirst(item); } else { Node oldPrev = target.prev; Node newNode = new Node(); newNode.item = item; target.prev = newNode; newNode.next = target; newNode.prev = oldPrev; oldPrev.next = newNode; itemCount++; } } public void addAfter(Item targetItem, Item item) { Node target = first; if (target == null) { throw new NullPointerException("No node in linked list."); } while (target != null && target.item != targetItem) { target = target.next; } if (target == null) { throw new NullPointerException("Can't find target node."); } if (target.next == null) { addLast(item); } else { Node oldNext = target.next; Node newNode = new Node(); newNode.item = item; target.next = newNode; newNode.prev = target; newNode.next= oldNext; oldNext.prev = newNode; itemCount++; } } } 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 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 注：实现链表使用的是pointer wrapper方式，这种方式的特点是prev/next指针包含在结点中，而数据由结点中的另一个指针（即item）所引用。采取这种方式，在获取结点数据时，我们需要进行double-dereferencing，而且这种方式实现的链表不是一种[局部化结构]，这意味着我们拿到链表的一个结点数据后，无法直接进行insert/delete操作。 常见面试题 输入一个链表，输出该链表中倒数第k个结点。 public class Solution { public ListNode FindKthToTail(ListNode head,int k) { //先求得链表的尺寸，赋值给size int size = 0; ListNode current = head; while (current != null) { size++; current = current.next; } //获取next实例域size-k次，即可得到倒数第k个结点（从1开始计数） for (int i = 0; i < size - k; i++) { head = head.next; } return head; } }

反转链表

public ListNode ReverseList(ListNode head) { if (head == null) { return null; } ListNode current = head; //原head的next node为null ListNode prevNode = null; ListNode newHead = null; while (current != null) { ListNode nextNode = current.next; current.next = prevNode; if (nextNode == null) { newHead = current; } prevNode = current; current = nextNode; } return newHead; }

以上转载