手写LinkedList

原作者：老铁123　　　
出处：https://blog.csdn.net/qewgd/article/details/85927616　　
本文归作者【老铁123】和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。

LinkedList
LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作;
实现 List 接口，能对它进行队列操作;
实现 Deque 接口，即能将LinkedList当作双端队列使用;
实现了Cloneable接口，即覆盖了函数clone()，能克隆;
实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输;
非同步;

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {}

实现代码如下

public class MyLinkedList<E> {

	private int size = 0;

	private Node<E> head;
	private Node<E> tail;

	public boolean add(E e) {
		size++;

		Node<E> l = tail;
		Node<E> newnode = new Node<E>(l, e, null);
		tail = newnode;
		if (null == l)
			head = newnode;
		else
			l.next = newnode;

		return true;
	}

	public E get(int index) {
		Node<E> temp = head;

		for (int i = 0; i < index; i++)
			temp = temp.next;

		return temp.data;
	}

	public E remove(int index) {
		Node<E> temp = head;
		for (int i = 0; i < index; i++)
			temp = temp.next;

		E data = temp.data;
		Node<E> pre = temp.pre;
		Node<E> next = temp.next;

		if (pre == null) {
			head = next;
		} else {
			pre.next = next;
			temp.pre = null;
		}

		if (next == null) {
			tail = pre;
		} else {
			next.pre = pre;
			temp.next = null;
		}

		temp.data = null;

		size--;

		return data;
	}

	public int getSize() {
		return size;
	}
}

class Node<E> {
	public Node<E> pre;
	public Node<E> next;
	public E data;

	public Node(Node<E> pre, E data, Node<E> next) {
		this.pre = pre;
		this.data = data;
		this.next = next;
	}
}