手寫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;
	}
}