代码如下：
/** * @ClassName LinkedList * @Description 链表 * @Author ouyangkang * @Date 2019-01-25 10:22 **/ public class LinkedList<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); } public String toString() { return e.toString(); } } //利用虚拟头节点 private Node dummyHead; private int size; public LinkedList() { dummyHead = new Node(null, null); size = 0; } public int getSize() { return size; } public boolean isEmpty() { return size == 0; } //在链表中添加一个元素 public void add(int index, E e) { if (index < 0 || index > size) { throw new IllegalArgumentException("add failed Illegal index"); } Node prv = dummyHead; for (int i = 0; i < index; i++) { prv = prv.next; } // Node node = new Node(e); // node.next = prv.next; // prv.next = node; prv.next = new Node(e, prv.next); size++; } //在链表头添加新元素 e public void addFirst(E e) { // Node node = new Node(e); // node.next = head; // head = node; add(0, e); } // 在链表尾部 public void addLast(E e) { add(size, e); } //获取链表的第index个位置的元素 // 在链表中不是一个常用操作 public E get(int index) { if (index < 0 || index > size) { throw new IllegalArgumentException("get failed Illegal index"); } 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 void set(int index, E e) { if (index < 0 || index > size) { throw new IllegalArgumentException("set failed Illegal index"); } Node cur = dummyHead.next; for (int i = 0; i < index; i++) { cur = cur.next; } cur.e = e; } // 是否包含 public boolean contains(E e) { Node cur = dummyHead.next; while (cur != null) { if (cur.e.equals(e)) { return true; } else { cur = cur.next; } } return false; } // 删除节点 返回节点值 public E remove(int index) { if (index < 0 || index > size) { throw new IllegalArgumentException("remove failed Illegal index"); } Node prev = dummyHead; for (int i = 0; i < index; i++) { prev = prev.next; } Node delNode = prev.next; prev.next = delNode.next; delNode.next = null; size--; return delNode.e; } public E removeFirst() { return remove(0); } public E removeLast() { return remove(size - 1); } public String toString() { StringBuilder res = new StringBuilder(); Node cur = dummyHead.next; while (cur != null) { res.append(cur + "->"); cur = cur.next; } res.append("NULL"); return res.toString(); } }有兴趣的可以写一个main方法测试一下。
数组和链表的扩展 我们可以根据上面写的Array类或者LinkedList类，实现一个队列，栈。只要你编写的队列，栈拥有一个Array类或者LinkedList类就可以实现了。下面我通过代码实现一下队列。队列是一种先进先出的数据结构，也就是First in First Out (FIFO)。代码如下：
/** * @ClassName ArrayQueue * @Description 数组实现队列 * @Author ouyangkang * @Date 2019-01-23 17:44 **/ public class ArrayQueue<E> implements Queue<E> { private Array<E> array; public ArrayQueue(){ array = new Array<>(); } public ArrayQueue(int capacity){ array = new Array<>(capacity); } @Override public void enQueue(E e) { array.addLast(e); } @Override public E deQueue() { return array.removeFirst(); } @Override public E getFront() { return array.getFirst(); } @Override public int getSize() { return array.getSize(); } @Override public boolean isEmpty() { return array.isEmpty(); } @Override public String toString(){ StringBuilder res = new StringBuilder(); res.append("Queue :"); res.append("front ["); for (int i = 0; i < array.getSize(); i++) { res.append(array.get(i)); if (i != array.getSize() - 1){ res.append(", "); } } res.append("] tail"); return res.toString(); } } /** * @ClassName LinkListQueue * @Description 链表实现队列 * @Author ouyangkang * @Date 2019-01-29 09:08 **/ public class LinkListQueue<E> implements Queue<E> { private class Node { public E e; public Node next; public Node(Node next, E e) { this.next = next; this.e = e; } public Node(E e) { this(null, e); } public Node() { this(null, null); } public String toString(){ return e.toString(); } } private Node head; private Node tail; private int size; @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 (isEmpty()) { throw new IllegalArgumentException("queue isEmpty"); } Node ret = head; head = head.next; ret.next = null; if (head == null) { tail = null; } size--; return ret.e; } @Override public E getFront() { if (isEmpty()) { throw new IllegalArgumentException("queue isEmpty"); } return head.e; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } public String toString() { StringBuilder res = new StringBuilder(); res.append("Queue: front "); Node cur = head; while (cur != null) { res.append(cur + "->"); cur = cur.next; } res.append("NULL tail"); return res.toString(); } }