说明：https://mp.csdn.net/mdeditor/94589662#
ArrayList 和 LinkedList都是List的实现类。ArrayList是通过维护一个数组实现，而LinkedList是通过维护链表实现的。
代码如下：
（两个结构的方法差不多，不过有些方法的复杂度不同，取决于他们的内部数据结构）
至于迭代器的实现，我是自己用内部类的方式。当然也可以用别的方式。
package code.hc.util;public class HLinkedList<E> implements HList<E>, HDeque<E> {private ListNode headNode;private ListNode tailNode;private int size;public HLinkedList(){headNode = null;tailNode = null;size = 0;}@Overridepublic HListIterator<E> listIterator() {return new HLinkedListIterator();}@Overridepublic void add(E e) {addLast(e);}@Overridepublic boolean isEmpty() {return headNode == null;}@Overridepublic HIterator<E> iterator() {return new HCollectionIterator();}@Overridepublic boolean contain(E e) {ListNode point = headNode;while(point != null){if(point.obj.equals(e))return true;point = point.next;}return false;}@Overridepublic void remove(E e) {if(headNode.obj.equals(e)){removeFirst();return;}ListNode curNode = headNode;while(curNode.next != null){if(e.equals(curNode.obj)){curNode.next = curNode.next.next;curNode.next.previous = curNode;size = size - 1;}}}@Overridepublic boolean remove(int index) {if(index < 0 || index >= size)return false;if(index == 0){ListNode tempNode = headNode.next;headNode = null;headNode = tempNode;headNode.previous = null;}else {ListNode father = headNode;while(index > 1){father = father.next;index = index - 1;}father.next = father.next.next;father.next.next.previous = father;}size = size - 1;return true;}@Overridepublic void clear() {while(headNode != null){ListNode nextNode = headNode.next;headNode = null;headNode = nextNode.next;headNode.previous = null;}tailNode = null;size = 0;}@Overridepublic int size() {return size;}@Overridepublic void addFirst(E e) {if(headNode == null){headNode = new ListNode(e);tailNode = headNode;}else {ListNode newNode = new ListNode(e);newNode.next = headNode;headNode.previous = newNode;headNode = headNode.previous;}size = size + 1;}@Overridepublic void addLast(E e) {if(tailNode == null){tailNode = new ListNode(e);headNode = tailNode;}else {ListNode newNode = new ListNode(e);newNode.previous = tailNode;tailNode.next = newNode;tailNode = tailNode.next;}size = size + 1;}@Overridepublic E getFirst() {if(headNode == null)return null;return headNode.obj;}@Overridepublic E getLast() {if(tailNode == null) return null;return tailNode.obj;}@Overridepublic void removeFirst() {if(headNode != null){ListNode nextNode = headNode.next;headNode = null;headNode = nextNode;headNode.previous = null;size = size - 1;}}@Overridepublic void removeLast() {if(tailNode != null){ListNode preNode = tailNode.previous;tailNode = null;tailNode = preNode;tailNode.next = null;size = size - 1;}}private class ListNode {private E obj;private ListNode next;private ListNode previous;ListNode(E o){obj = o;next = null;previous = null;}}private class HLinkedListIterator implements HListIterator<E>{private ListNode curNode;private HLinkedListIterator(){curNode = headNode;}@Overridepublic boolean hasPrevious() {return curNode != null;}@Overridepublic E previous() {E node = curNode.obj;curNode = curNode.previous;return node;}@Overridepublic boolean hasNext() {return curNode != null;}@Overridepublic E next() {E node = curNode.obj;curNode = curNode.next;return node;}}private class HCollectionIterator implements HIterator<E> {private ListNode curNode;private HCollectionIterator(){curNode = headNode;}@Overridepublic boolean hasNext() {return curNode != null;}@Overridepublic E next() {E node = curNode.obj;curNode = curNode.next;return node;}}
}