链表的实现

/**

• 实现一个链表结构
• @author guofeng
• 添加元素：
• 链表头： O(1)
• 链表尾： O(n)
• 删除头: O(1)
• 删除尾： O(n)
• 修改： O(n)
• 查找：O(n)

*/

public class LinkedList<E> {
	private class Node {
		private E e;
		private 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 int size = 0;
//	private Node head = null;
	private Node dummyHead; 
	public LinkedList () {
		dummyHead = new Node(null, null);
		size = 0;
	}
	
	public int getSize() {
		return size;
	}
	
	public boolean isEmpty() {
		return size == 0;
	}
	
	// 为链表头添加一个元素
	public void addFirst(E e) {
		add(0, e);
	}
	
	// 在其它位置添加链表
	public void add(int index, E e) {
		if(index < 0 || index > size) {
			throw new IllegalArgumentException("Add failed. Illegal index.");
		}
		Node prev = dummyHead;
		for(int i = 0; i < index; i ++) {
			prev = prev.next;
		}
//		Node node = new Node(e);
//		node.next = prev.next;
//		prev.next = node;
//		上面写法等于下面写法
		prev.next = new Node(e, prev.next);
		// 维护下size
		size ++;
	}
	
	// 在链表末尾添加元素
	public void addLast(E e) {
		add(size, e);
	}
	
	// 获取链表中的第 index 个位置的元素
	// 不常用，只是练习用
	
	public E get(int 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);
	}
	
	// 修改链表中第index 个元素
	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;
	}
	
	// 查找链表中是否有元素e
	public boolean contains(E e) {
		Node cur = dummyHead.next;
		while(cur != null) {
			if(cur.e.equals(e)) {
				return true;
			}
			cur = cur.next;
		}
		return false;
	}
	
	// 删除链表中第index个元素
	public E remove(int index) {
		Node pre = dummyHead;
		if(index < 0 || index >= size) {
			throw new IllegalArgumentException("set failed, Illegal index.");
		}
		for(int i = 0; i < index; i ++) {
			pre = pre.next;
		}
		Node retNode = pre.next;
		pre.next = retNode.next;
		retNode.next = null;
		size --;
		return retNode.e;
	}
	
	// 删除链表中的第一个元素
	public E removeFirst() {
		return remove(0);
	}
	
	// 删除链表中的最后一个元素
	public E removeLast() {
		System.out.println("size: "+ size);
		return remove(size - 1);
	}
	
	// 链表的遍历
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		Node cur = dummyHead.next;
		while(cur != null) {
			sb.append(cur + "->");
			cur = cur.next;
		}
		sb.append("NULL");
		return sb.toString();
	}
}