真正的动态数据结构（引用和指针）
优点:真正的动态，不需要处理固定容量的问题。
缺点:丧失随机访问的能力。
链表就像寻宝，我们拿到藏宝图开始出发寻宝，每找到一个地方后，里面藏着下一步应该去哪里寻找。一步一步往下找，就能找到宝藏。每个节点都存有数据和下个节点的位置。
将数据存储在节点中,next指向当前节点的下一个节点。
class Node { E e; Node next; }
要想访问这个链表的所有节点，我们必须知道链表的头节点，所以我们定义head，在定义个size记录链表中有几个元素
向链表的头添加元素很简单，我们添加一个node，在把这个nodet指针指下一个节点，这时的head节点就变成我们添加的节点，我们就变成头节点。
所以LinkList类
package com.dsideal.test; public class LinkList<E> { private class Node { public E e; public Node next; public Node(E e, Node next) { this.e = e; this.next = next; } public Node(E e) { this(e,null); } public Node() { this(null,null); } @Override public String toString() { return e.toString(); } } private Node head; private int size; public LinkList() { head = null; size = 0; } public int getSize() { return size; } public boolean isEmpty() { return size == 0; } public void addFirst(E e) { // Node node = new Node(e); // node.next = head; // head = node; head = new Node(e,head); size ++; } }
在链表中间添加元素，我们必须知道在插入节点之前的一个节点是什么。将前一个节点的指针指向我们插入的节点，把我们的插入节点的指针指向下一个节点。
package com.dsideal.test;
public class LinkList<E> { private class Node { public E e; public Node next; public Node(E e, Node next) { this.e = e; this.next = next; } public Node(E e) { this(e,null); } public Node() { this(null,null); } @Override public String toString() { return e.toString(); } } private Node head; private int size; public LinkList() { head = null; size = 0; } public int getSize() { return size; } public boolean isEmpty() { return size == 0; } public void addFirst(E e) { // Node node = new Node(e); // node.next = head; // head = node; head = new Node(e,head); size ++; } public void add(int index,E e) { if (index < 0 || index > size) { throw new IllegalArgumentException("add is fail,index < 0 or index >= size"); } if (index == 0) { addFirst(e); }else { Node prev = head; for (int i = 0;i < index - 1;++i) { prev = prev.next; } // Node node = new Node(e); // node.next = prev.next; // prev.next = node; prev.next = new Node(e,prev.next); size ++; } } public void addLast(E e) { add(size,e); } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("Link head:"); Node cur = head; while (cur != null) { res.append(cur + "->"); cur = cur.next; } res.append("NULL"); return res.toString(); } }
这时我们发现，当add插入index等于零的时候，要做个判断。所以我们引入一个虚拟的头节点。Node dunmmy = new Node(null,null);删除节点，找到要删除节点的上一个节点，将
他的指针指向删除节点的下一个节点，将我们删除节点的next指向null。
所以LinkLIst类变为
public class LinkList<E> { private class Node { public E e; public Node next; public Node(E e, Node next) { this.e = e; this.next = next; } public Node(E e) { this(e, null); } public Node() { this(null, null); } @Override public String toString() { return e.toString(); } } private Node dummyHead; private int size; public LinkList() { dummyHead = new Node(null, null); size = 0; } //获取链表元素个数 public int getSize() { return size; } //链表是否为空 public boolean isEmpty() { return size == 0; } //增加链表头元素 public void addFirst(E e) { // Node node = new Node(e); // node.next = head; // head = node; add(0, e); } //增加链表元素个数 public void add(int index, E e) { if (index < 0 || index > size) { throw new IllegalArgumentException("index < 0 or index > size,add is fail."); } Node prev = dummyHead; for (int i = 0; i < index; i++) { prev = prev.next; } // Node node = new Node(e); // node.next = prev.next; // prev.next = node; prev.next = new Node(e, prev.next); size++; } //添加链表末尾元素 public void addLast(E e) { add(size, e); } //获取元素index public E get(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("get is fail,index < 0 or index > size"); } Node cur = dummyHead.next; for (int i = 0;i < index;++i) { cur = cur.next; } return cur.e; } //获取第一个元素 public E getFirst() { return get(0); } //获取最后一个元素 public E getLast() { return get(size - 1); } //判读是否包含 public boolean contains(E e) { Node cur = dummyHead.next; while (cur != null) { if (cur.e.equals(e)) { return true; } cur = cur.next; } return false; } //修改值 public void set(int index,E e) { if (index < 0 || index >= size) { throw new IllegalArgumentException("set is fail,index < 0 or index > size"); } Node cur = dummyHead.next; for (int i = 0;i < index;++i) { cur = cur.next; } cur.e = e; } //删除元素 public E remove(int index) { if (index < 0 || index >= size) { } Node prev = dummyHead; for (int i = 0;i < index;++i) { prev = prev.next; } //删除的元素 Node retNode = prev.next; prev.next = retNode.next; retNode.next = null;//删除元素的指向下一个地址为空 size-- ; return retNode.e; } //删除第一元素 public E removeFirst() { return remove(0); } //删除最后一个元素 public E removeLast() { return remove(size - 1); } @Override public String toString() { StringBuilder res = new StringBuilder(""); for (Node cur = dummyHead.next; cur != null; cur = cur.next) { res.append(cur + "->"); } res.append("NULL"); return res.toString(); } }
用链表实现栈
public class LinkListStack<E> implements Stack<E> { private LinkList<E> linkList; public LinkListStack() { linkList = new LinkList<>(); } @Override public int getSize() { return linkList.getSize(); } @Override public boolean isEmpty() { return linkList.isEmpty(); } @Override public void push(E e) { linkList.addFirst(e); } @Override public E pop() { return linkList.removeFirst(); } @Override public E peek() { return linkList.getFirst(); } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("Stack top["); res.append(linkList); res.append("] tail"); return res.toString(); } }
链表实现队列，优化算法变为O(1)级别的
public class LinkListQueue<E> implements Queue<E> { //内置节点 private class Node { public E e; public Node next; public Node(E e,Node next) { this.e = e; this.next = next; } public Node(E e) { this(e,null); } public Node() { this(null,null); } @Override public String toString() { return e.toString(); } } private Node head,tail; private int size; public LinkListQueue() { head = null; tail = null; size = 0; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public void enqueue(E e) { if (tail == null) { tail = new Node(e); head = tail; }else { tail.next = new Node(e); tail = tail.next; tail.next = null; } size ++; } @Override public E dequeue() { if (isEmpty()) { throw new IllegalArgumentException("dequeue is fail,queue is isEmpty"); } Node retNode = head; head = retNode.next; retNode.next = null; if (head == null) { tail = null; } size--; return retNode.e; } @Override public E getFront() { if (isEmpty()) { throw new IllegalArgumentException("Queue is isEmpty,so getFront is fail."); } return head.e; } @Override public String toString() { StringBuffer str = new StringBuffer(""); str.append("LinkListQueue: head:"); Node cur = head; while (cur != null) { str.append(cur + "->"); cur = cur.next; } str.append("NULL"); return str.toString(); } }