java单链表-带头结点和不带头结点单链表的简单实现

带头结点的单链表实现

public class LinkedList<T> {
	private Entry<T> head, tail; //头指针，尾指针  
	private int size; //通过一个变量记录链表长度 

	public LinkedList() {
       //生成一个头结点,让头指针和尾指针都指向它  
		head = tail = new Entry<T>(null);
		size = 0;
	}

	public int size() {
		return size;
	}

	public boolean isEmpty() {
		return head.next == null; //当头结点的next为空,表明整个链表为空
	}

	public T get(int index) {
		return current(index).element;
	}

	public T set(int index, T element) {
		Entry<T> entry = current(index);
		T oldVal = entry.element;
		entry.element = element;
		return oldVal;
	}

    //默认在原链表尾部添加新的结点
	public boolean add(T element) {
		Entry<T> newEntry = new Entry<T>(element);
		tail.next = newEntry;//原链表尾指针的next指向新的结点  
		tail = newEntry;//尾指针向后移动一位，指向新的结点  
		size++;
		return true;
	}

	public boolean add(int index, T element) {
        //若索引值和链表长度一样，新结点添加到链表最后位置  
		if (index == size)
			return add(element);

        //得到索引index的前一个结点
		Entry<T> preEntry = previous(index);
        //新结点的next为preEntry的next指向的结点
		Entry<T> newEntry = new Entry<T>(element, preEntry.next);
        //preEntry的next指向新的结点
		preEntry.next = newEntry;
		size++;
		return true;
	}

	public T remove(int index) {
        //得到索引index的前一个结点
		Entry<T> preEntry = previous(index);
		T oldVal = preEntry.next.element;
        //如果preEntry的next刚好是最后一个结点，修改tail为preEntry 
		if (preEntry.next == tail)
			tail = preEntry;
		preEntry.next = preEntry.next.next;
		size--;
		return oldVal;
	}

	public void clear() {
		head.next = null;
		tail = head;
		size = 0;
	}

	public String toString() {
		String result = "[";
		Entry<T> entry = head.next;
		while (entry != null) {
			result += entry.element;
			entry = entry.next;
			if (entry != null)
				result += ", ";
		}
		return result + "]";
	}

    //获得索引index对应的entry 
	public Entry<T> current(int index) {
		checkIndexBounds(index);
		Entry<T> entry = head.next;//从第一个结点开始遍历
		int c = 0;
		while (entry != null && c < index) {
			entry = entry.next;
			c++;
		}
		return entry;
	}

    //获得索引index-1对应的entry  
	public Entry<T> previous(int index) {
		checkIndexBounds(index);
		Entry<T> entry = head;//从头结点开始遍历，头指针指向头结点 
		int c = 0;
		while (entry.next != null && c < index) {
			entry = entry.next;
			c++;
		}
		return entry;
	}

	private void checkIndexBounds(int index) {
		if (index < 0 || index >= size)
			throw new IndexOutOfBoundsException("[index: " + index + ", size: "
					+ size + "]");
	}

    //结点对象  	
	private static class Entry<T> {
		T element;
		Entry<T> next;

		public Entry(T element) {
			this(element, null);
		}

		public Entry(T element, Entry<T> next) {
			this.element = element;
			this.next = next;
		}
	}
}

不带头结点的单链表实现

public class LinkedList<T> {
	private Entry<T> head, tail;
	private int size;

	public LinkedList() {
		head = tail = null;
		size = 0;
	}

	public int size() {
		return size;
	}

	public boolean isEmpty() {
		return head == null; //头指针为空，表示整个链表为空
	}

	public T get(int index) {
		return current(index).element;
	}

	public T set(int index, T element) {
		Entry<T> entry = current(index);
		T oldVal = entry.element;
		entry.element = element;
		return oldVal;
	}

	public boolean add(T element) {
		Entry<T> newEntry = new Entry<T>(element);
		if (head == null) //如果头指针为空，直接将新结点赋值给头指针和尾指针
			head = tail = newEntry;
		else {
			tail.next = newEntry; //否则，尾指针的next指向新的结点，尾指针后移一位，指向新的结点
			tail = newEntry;
		}
		size++;
		return true;
	}

	public boolean add(int index, T element) {
       //若索引值和链表长度一样，新结点添加到链表最后位置  
		if (index == size)
			return add(element);

		//获得索引值为index-1的结点
		Entry<T> preEntry = previous(index);
		Entry<T> newEntry = new Entry<T>(element);
		if (preEntry == null) { //index=0 直接操作头指针
			newEntry.next = head;
			head = newEntry;
		} else { //其他情况，用获得的前一个结点完成添加操作
			newEntry.next = preEntry.next;
			preEntry.next = newEntry;
		}
		size++;
		return true;
	}

	public T remove(int index) {
        //获得索引值为index-1的结点
		Entry<T> preEntry = previous(index);
		T oldVal;
		if (preEntry == null) {//index=0 直接操作头指针
			oldVal = head.element;
			head = head.next;
		} else { //其他情况，用获得的前一个结点完成移除操作
			oldVal = preEntry.next.element;
            //如果preEntry的next刚好是最后一个结点，修改tail为preEntry 			
			if (tail == preEntry.next)
				tail = preEntry;
			preEntry.next = preEntry.next.next;
		}
		size--;
		return oldVal;
	}

	public void clear() {
		head = tail = null;
		size = 0;
	}

	public String toString() {
		String result = "[";
		Entry<T> entry = head;
		while (entry != null) {
			result += entry.element;
			entry = entry.next;
			if (entry != null)
				result += ", ";
		}
		return result + "]";
	}

	public Entry<T> current(int index) {
		checkIndexBounds(index);
		Entry<T> entry = head;
		int c = 0;
		while (entry != null && c < index) {
			entry = entry.next;
			c++;
		}
		return entry;
	}

	public Entry<T> previous(int index) {
		checkIndexBounds(index);
		if (index == 0) //索引为0 直接返回null，表明直接用头指针完成操作即可
			return null;

		Entry<T> entry = head;
		int c = 0;
		while (entry.next != null && c < index - 1) {
			entry = entry.next;
			c++;
		}
		return entry;
	}

	private void checkIndexBounds(int index) {
		if (index < 0 || index >= size)
			throw new IndexOutOfBoundsException("[index: " + index + ", size: "
					+ size + "]");
	}

	private static class Entry<T> {
		T element;
		Entry<T> next;

		public Entry(T element) {
			this(element, null);
		}

		public Entry(T element, Entry<T> next) {
			this.element = element;
			this.next = next;
		}
	}
}