动态数据结构
网络异常，图片无法展示
|
链表的特征
网络异常，图片无法展示
|
网络异常，图片无法展示
|
数组和链表的对比
网络异常，图片无法展示
|
链表的设计
表头添加元素
网络异常，图片无法展示
|
在中间添加元素
关键是找到待添加节点的前一个节点。
如果不设置虚拟头结点，由于head没有钱一个节点，所以就需要对头结点进行特殊的处理。
网络异常，图片无法展示
|
网络异常，图片无法展示
|
删除元素
网络异常，图片无法展示
|
这里最主要的是获取当前节点的前一个节点和当前节点。
- 获取当前节点
/** * index = 2 * 1, 2, 3, 4 * cur = dummyHead.next = 1, i < index => i < 2 * i = 0; cur = 2 * i = 1; cur = 3; */ Node cur = dummyHead.next; for(int i = 0; i < index; i++) { cur = cur.next; }
- 获取当前节点的前一个节点
/** * index = 2 * 1, 2, 3, 4 * prev = dummyHead = null, i < index => i < 2 * i = 0; cur = 1 * i = 1; cur = 2; */ Node prev = dummyHead; for(int i = 0; i < index; i++) { prev = prev.next; }
代码实现
public class LinkedList<E> { private Node dummyHead; private int size; private class Node { public E e; public Node next; public Node(E e, Node next) { this.next = next; this.e = e; } public Node(E e) { this.e = e; } public Node() { this(null, null); } @Override public String toString() { return e.toString(); } } public LinkedList() { // 链表中本身存在一个空节点，虚拟节点。 this.dummyHead = new Node(null, null); this.size = 0; } // 获取元素个数 public int getSize() { return size; } // 判断是否为空 public boolean isEmpty() { return size == 0; } // 头部添加元素 public void addFirst(E e) { // 先创建一个node节点 // Node node = new Node(e); // node.next = head; // head = node; // head = new Node(e, head); add(0, e); } // 在中间添加节点 public void add(int index, E e) { if(index > size && index < 0) { throw new Error("add fail, index > size && index < 0"); } // 先创建一个prev节点，来查找预添加节点的前一个节点。 Node prev = dummyHead; // 这里的边界是index。因为prev开始是等于第一个节点之前的空节点的。 for(int i = 0; i < index; i++) { prev = prev.next; } Node node = new Node(e); node.next = prev.next; prev.next = node; size++; } // 从尾部添加节点 public void addLast(E e) { add(size - 1, e); } // 查找元素 public E get(int index) { /** * index = 2 * 1, 2, 3, 4 * cur = dummyHead.next = 1, i < index => i < 2 * i = 0; cur = 2 * i = 1; cur = 3; */ Node cur = dummyHead.next; for(int i = 0; i < index; i++) { cur = cur.next; } return cur.e; } // 确定是否有该元素 public boolean contains(E e) { Node cur = dummyHead.next; for(int i = 0; i < size; i++) { if(cur.e == e) { return true; } cur = cur.next; } return false; } // 修改元素 public void set(int index, E e) { if(index < 0 || index >= size) { throw new Error("set fail, index < 0 || index >= size"); } Node cur = dummyHead; for(int i = 0; i < index; i++) { cur = cur.next; } cur.e = e; } // 删除元素 public E remove(int index) { if(index > size && index < 0) { throw new Error("remove fail, index > size && index < 0"); } // 找到待删除节点之前的节点。 /** * index = 2 * 1, 2, 3, 4 * prev = dummyHead = null, i < index => i < 2 * i = 0; cur = 1 * i = 1; cur = 2; */ Node prev = dummyHead; for(int i = 0; i < index; i++) { prev = prev.next; } // 将prev的next指向下下一个元素。 Node cur = prev.next; prev.next = cur.next; size--; return cur.e; } public E removeFirst() { return remove(0); } public E removeLast() { return remove(size - 1); } // 通过指定元素删除元素 public void removeElement(E e) { Node prev = dummyHead; // 从头开始遍历 while(prev.next != null) { if(e.equals(prev.next.e)) { prev.next = prev.next.next; prev.next.next = null; size--; } prev = prev.next; } } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("LinkedList: "); Node cur = dummyHead.next; while(cur != null) { res.append(cur.e + "=>"); cur = cur.next; } return res.toString(); } }
复杂度分析
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
用链表设计栈结构
我们可以使用链表头部作为栈顶结构。
网络异常，图片无法展示
|
public class StackByLinkedList<E> implements StackInterface<E> { // 我们可以使用链表头部作为栈顶结构。 private LinkedList<E> list; public StackByLinkedList() { list = new LinkedList(); } @Override public void push(E e) { list.addFirst(e); } @Override public E pop() { return list.removeFirst(); } @Override public int getSize() { return list.getSize(); } @Override public E peek() { return list.get(0); } @Override public boolean isEmpty() { return list.isEmpty(); } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("linkedListStack top: "); res.append(list); return res.toString(); } }
用链表设计队列结构
这里需要注意的是，当队列中只有一个元素时，删除了元素，需要将tail指针指向null。
网络异常，图片无法展示
|
public class LinkedListQueue<E> implements QueueInterface<E> { // 节点总数 private int size; // 头部节点 private Node head; // 尾部节点 private Node tail; private class Node { public E e; public Node next; public Node(E e) { this.e = e; } public Node(E e, Node next) { this.e = e; this.next = next; } public Node() { this(null, null); } @Override public String toString() { return e.toString(); } } public LinkedListQueue() { this.size = 0; this.head = null; this.tail = null; } // 入队 @Override public void enqueue(E e) { // 需要先判断队列是否为空 if(tail == null) { tail = new Node(e); head = tail; }else { // 改变尾节点指向。 tail.next = new Node(e); tail = tail.next; } size++; } @Override public E dequeue() { if(head == null) { throw new Error("linkedListQueue is empty"); } E cur = head.e; head = head.next; // 如果队列中只有一个元素，那么删除后需要改变tail指向 if(head == null) { tail = null; } size--; return cur; } @Override public E getFront() { return head.e; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("LinkedListQueue : "); Node cur = head; while(cur != null) { res.append(cur.e + "=>"); cur = cur.next; } return res.toString(); } }
移除链表元素 LeetCode-203
- 方式一：删除头结点时另做考虑
class Solution { public ListNode removeElements(ListNode head, int val) { // 查看头部节点是否为val元素。可能删除后下一个节点依旧是val。 while(head != null && head.val == val) { head = head.next; } // 当删除头部节点时，链表为空，则返回false. if(head == null) { return null; } // 判断中间元素是否是val ListNode prev = head; while(prev.next != null) { // 查找到了，将跳跃一个元素 if(prev.next.val == val) { prev.next = prev.next.next; }else { // 没有查到，将指向下一个元素继续。 prev = prev.next; } } return head; } }
- 方式二： 创建一个虚拟头结点。 注意: 这个虚拟节点的next始终指向头结点。给出虚拟头结点的作用是为了可以统一处理头结点和中间节点。因为我们需要找到的是待删除元素的前一个元素。
class Solution { public ListNode removeElements(ListNode head, int val) { // 创建一个虚拟节点。并且next始终指向头结点。 ListNode dummyHead = new ListNode(-1); dummyHead.next = head; // 创建一个查询的前一个节点 ListNode prev = dummyHead; while(prev.next != null) { if(prev.next.val == val) { prev.next = prev.next.next; }else { prev = prev.next; } } return dummyHead.next; } }
