链表-java实现双向链表

    前面已经总结了单向链表，有兴趣的兄弟可以进我博客看一下。http://mountain-king.iteye.com/blog/715651。。大家对比就可以看出，实现同样的功能单向链表要比双向链表痛苦的多。所以呀不断地总结前辈留下的东西，是社会进步的基础呀。可以直接看LinkedList的源码，其就是个双向链表。

 

一、双向链表的结构。

     (1)、首先节点的结构，其中包含本节点内容，同时需要知道前面是谁后面是谁。 

private static class Entry<E> {
		//元素
		E e;
		//后一个节点
		Entry<E> nextEntry;
		//前一个节点
		Entry<E> previousEntry;

		public Entry(E e, Entry<E> previousEntry, Entry<E> nextEntry) {
			this.e = e;
			this.nextEntry = nextEntry;
			this.previousEntry = previousEntry;
		}
	}

 其中e则指向本节点的元素，而nextEntry则指向下一个节点，previousEntry则指向前一个节点。

 

     (2)、需要定义一个节点，其同时知道表头，同时知道表尾，这里就暂时定义为head。

private transient Entry<E> head = new Entry<E>(null, null, null);

public DoubleChain() {
		head.nextEntry = head.previousEntry = head;
	}

 可以看出，在初始化方法中，直接将表头和表尾直接都指向head。这样在head的基础上不管怎么增加元素都逃脱不了与head关系。牢记head.nextEntry表头，head.previousEntry表尾。

 

     (3)、同样记录节点的个数只是为了提高效率，不是必要。

private int size;

public int size() {
		return this.size;
	}

  好了有这三样，就足够了。就看我们如何用他们了。

 

二、内部实现。

    (1)、方法addBefore。由于一开始就初始化了head，有了head作为基准，玩转整个链表也就靠这个方法了。

private void addBefore(E e, Entry<E> entry) {
		//新节点的初始化，指定新节点的前一个节点和后一个节点
		Entry<E> newEntry = new Entry<E>(e, entry.previousEntry, entry);
		//告知新节点的前一个节点其后面是新节点
		newEntry.previousEntry.nextEntry = newEntry;
		//告知新节点的后一个节点其前节点是新节点
		newEntry.nextEntry.previousEntry = newEntry;
		size++;
	}

 可以看出，通过指定的元素创建一个新的节点。然后将其前前后后的关系都打通就好了。

 

    (2)、表头插入。再简单不过了，直接在head.nextEntry前增加就好了，直接调用addBefore。效率高

public void addHead(E e) {
		this.addBefore(e, head.nextEntry);
	}

 

    (3)、尾插入。同样简单，直接在head.previous前增加就好了，同样调用addBefore。效率高

public void add(E e) {
		this.addBefore(e, head);
	}

 

 

   (4)、指定节点插入（插队）。同样需要插队，但是由于其节点的双向性，则不需要进行特殊处理，直接循环找出指定的节点元素就好了。效率低

public void addSpecifyIndex(E e, int index) {
		int count = 0;
		for (Entry<E> p = head.nextEntry; p != head; p = p.nextEntry) {
			if (count == index) {
				this.addBefore(e, p);
				return;
			}
			count++;
		}
	}

   

    (5)、指定节点获取元素。同样循环找出。效率低

public E get(int index) {
		int count = 0;
		E result = null;
		for (Entry<E> p = head.nextEntry; p != head; p = p.nextEntry) {
			if (count == index) {
				result = p.e;
			}
			count++;
		}
		return result;
	}

 

    (6)、指定节点删除。同理，找到要删除的节点，让指定节点的前后直接相通就OK了。效率低

public void remove(int index) {
		int count = 0;
		for (Entry<E> p = head.nextEntry; p != head; p = p.nextEntry) {
			if (count == index) {
				p.previousEntry.nextEntry= p.nextEntry;
				p.nextEntry.previousEntry=p.previousEntry;
				size--;
				return;
			}
			count++;
		}
	}

 

    (7)、循环。为了好进行遍历演示，下面的就是循环遍历所用的了，大家随意看一下就好了。

private Entry<E> current;

public boolean hasNext() {
		return current != head;
	}

	public E next() {
		E result = current.e;
		current = current.nextEntry;
		return result;
	}

	public void setCursor(int index) {
		int count = 0;
		for (Entry<E> p = head.nextEntry; p != head; p = p.nextEntry) {
			if (count == index) {
				current = p;
			}
			count++;
		}

 

三、测试。。一个main方法，测试一下。

public static void main(String[] args) {
		DoubleChain<String> doubleChain = new DoubleChain<String>();
		for (int i = 0; i < 4; i++) {
			doubleChain.add(i + "");
		}
		// 头插入
//		 doubleChain.addHead("head");
//		// 尾插入
//		 doubleChain.add("tail");
//		// 指定节点插入
//		 doubleChain.addSpecifyIndex("Specify", 1);
//		// 指定节点删除
//		 doubleChain.remove(3);
//		// 设置循环的初始节点
//		doubleChain.setCursor(0);
		int count = 0;
		System.out.println("######SIZE" + doubleChain.size() + "#######");
		while (doubleChain.hasNext()) {
			System.out.println("index:" + count + ",entry:"
					+ doubleChain.next());
			count++;
		}

		System.out.println(doubleChain.get(doubleChain.size() - 2));

	}

 

四、总结。。

   可以看出，从结构上讲，双向链表和单项链表最大的区别在于每个节点都是双向的。从效率上讲，提高了尾插入的效率，但是对于插队同样效率不高。如果需要反复进行插队操作的同学注意了，LinkedList的效率会很低的哦。

 

五、全部代码。。

package paladin.chain;


public class DoubleChain<E> implements Chain<E> {

	private transient Entry<E> head = new Entry<E>(null, null, null);

	private Entry<E> current;

	private int size;

	public DoubleChain() {
		head.nextEntry = head.previousEntry = head;
	}

	
	private void addBefore(E e, Entry<E> entry) {
		//新节点的初始化，指定新节点的前一个节点和后一个节点
		Entry<E> newEntry = new Entry<E>(e, entry.previousEntry, entry);
		//告知新节点的前一个节点其后面是新节点
		newEntry.previousEntry.nextEntry = newEntry;
		//告知新节点的后一个节点其前节点是新节点
		newEntry.nextEntry.previousEntry = newEntry;
		size++;
	}

	public void add(E e) {
		this.addBefore(e, head);
	}

	public void addHead(E e) {
		this.addBefore(e, head.nextEntry);
	}

	public void addSpecifyIndex(E e, int index) {
		int count = 0;
		for (Entry<E> p = head.nextEntry; p != head; p = p.nextEntry) {
			if (count == index) {
				this.addBefore(e, p);
				return;
			}
			count++;
		}
	}

	public void remove(int index) {
		int count = 0;
		for (Entry<E> p = head.nextEntry; p != head; p = p.nextEntry) {
			if (count == index) {
				p.previousEntry.nextEntry= p.nextEntry;
				p.nextEntry.previousEntry=p.previousEntry;
				size--;
				return;
			}
			count++;
		}
	}

	public E get(int index) {
		int count = 0;
		E result = null;
		for (Entry<E> p = head.nextEntry; p != head; p = p.nextEntry) {
			if (count == index) {
				result = p.e;
			}
			count++;
		}
		return result;
	}

	public boolean hasNext() {
		return current != head;
	}

	public E next() {
		E result = current.e;
		current = current.nextEntry;
		return result;
	}

	public void setCursor(int index) {
		int count = 0;
		for (Entry<E> p = head.nextEntry; p != head; p = p.nextEntry) {
			if (count == index) {
				current = p;
			}
			count++;
		}

	}

	public int size() {
		return this.size;
	}

	private static class Entry<E> {
		//元素
		E e;
		//后一个节点
		Entry<E> nextEntry;
		//前一个节点
		Entry<E> previousEntry;

		public Entry(E e, Entry<E> previousEntry, Entry<E> nextEntry) {
			this.e = e;
			this.nextEntry = nextEntry;
			this.previousEntry = previousEntry;
		}
	}

	public static void main(String[] args) {
		DoubleChain<String> doubleChain = new DoubleChain<String>();
		for (int i = 0; i < 4; i++) {
			doubleChain.add(i + "");
		}
		// 头插入
//		 doubleChain.addHead("head");
//		// 尾插入
//		 doubleChain.add("tail");
//		// 指定节点插入
//		 doubleChain.addSpecifyIndex("Specify", 1);
//		// 指定节点删除
//		 doubleChain.remove(3);
//		// 设置循环的初始节点
//		doubleChain.setCursor(0);
		int count = 0;
		System.out.println("######SIZE" + doubleChain.size() + "#######");
		while (doubleChain.hasNext()) {
			System.out.println("index:" + count + ",entry:"
					+ doubleChain.next());
			count++;
		}

		System.out.println(doubleChain.get(doubleChain.size() - 2));

	}

}