实现LinkedList

数据存储在节点中

class Node {
    E e;
    Node next;
}

• 优点：不需要处理固定容量的问题，做到真正的动态
• 缺点：丧失了随机访问的能力

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 head;
	private int size;
	
	public LinkedList() {
		this.head = null;
		this.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 failed,Illegal index is error");
		}
		
		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);
	}
}

虚拟节点

• 解决头节点插入与其他节点插入方法不同的问题

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() {
		this.dummyHead = new Node(null, null);
		this.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 is error");
		}
		Node prev = dummyHead;
		for (int i = 0; i < index; i++) {
			prev = prev.next;
		}
		prev.next = new Node(e,prev.next);
		size++;
	}

	// 在链表末尾添加元素
	public void addLast(E e) {
		add(size, e);
	}

	// 在链表头添加元素
	public void addFirst(E e) {
		add(0,e);
	}

	// 获取链表的index的值
	public E get(int index) {
		if (index < 0 || index > size) {
			throw new IllegalArgumentException("Add failed,Illegal index is error");
		}
		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("Add failed,Illegal index is error");
		}
		Node cur = dummyHead;
		for (int i = 0; i < index; i++) {
			cur = cur.next;
		}
		cur.e = e;
	}

	// 查找链表是否存在元素e
	public boolean contains(E e) {
		Node cur = dummyHead.next;
		while (cur != null) {
			if (cur.e.equals(e)) {
				return true;
			}
		}
		return false;
	}

	// 删除指定元素
	public E remove(int index) {
		if (index < 0 || index > size) {
			throw new IllegalArgumentException("Add failed,Illegal index is error");
		}
		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);
	}

	@Override
	public String toString() {
		StringBuilder res = new StringBuilder();
		// Node cur = dummyHead.next;
		// while(cur != null) {
		//	res.append(cur + "->");
		//	cur = cur.next;
		// }
		for (Node cur = dummyHead.next; cur != null; cur = cur.next) {
			res.append(cur + "->");
		}
		res.append("NULL");
		return res.toString();
	}
}