双向链表之我的理解

谈到数据结构性能, 时常被问到List和Link的区别, 在回答之后,不可能避免的会将问题的焦点引到这两种存储方式的底层实现上来. List较为简洁,线形存储即可,而Link基本结构, 则是考察的重点.例如说,双向链表.Java JDK中的java.util.LinkedList就是一个双链表。

 

双向链表的结构如下，每个节点包括3个属性(前节点引用，后节点引用，数值)。这两个引用,指向它的前后的节点,这样就克服普通链表只能向后遍历的局限: (自己画的图真丑！！！)

 

来张网上的截图，H为头节点，value为null，它的引用分别指向最前和最后的两个节点。这样从两头可以遍历整个链表。

[疑问]：在Java数据结构和算法(第二版)中，第一个节点的prev和最后一个节点的next指向的null，而网上的例子都指向head节点，望看到的回复下,谢谢了。

双向链表的插入：

双向链表的删除：

插入和删除是链表的优势所在，只需要改变４个引用的指向即可。而List则需移动改节点后面的所有元素，相对效率差了很多。

 

参考了网上很多代码实现，结合Java的面向对象的特点，整理了一份源码，如下：

 

文件一: MyList 接口, 仅一个实现类的情况下,可无视.

/**
 * 仅添加几个主要的功能方法.
 * size,isEmpty较为简单,未考虑
 * @author 完美天龙
 *
 */
public interface MyList {
	public void add(Object o);
	public void delete(int i);
	public void addLast(Object o);
	public void addFirst(Object o);
	public Object get(int i);
}

文件二:功能的实现类, 实现了MyList接口, 并拥有自己的具体实现方法.我加了很多注释,只要自己用心去看.肯定能理解.

 

public class MyDoubleLinkedList implements MyList {
	private Node head = new Node(null);
	private int size = 0;

	/**
	 * 新节点加添,默认至链表最尾段, 也就是head的前面.
	 * 
	 * @param o
	 */
	public void add(Object o) {
		addBefore(new Node(o), head);
	}

	/**
	 * 删除指定的节点
	 * 
	 * @param o
	 */
	public void delete(int i) {
		removeNode(getNodeByIndex(i));

	}

	/**
	 * 查询指定位置的节点的value
	 * 
	 * @param i
	 * @return
	 */
	public Object get(int i) {
		return getNodeByIndex(i).getValue();
	}

	/**
	 * 添加节点至链表的尾端,即添加至head之前.
	 * 
	 * @param o
	 */
	public void addLast(Object o) {
		addBefore(new Node(o), head);
	}

	/**
	 * 添加节点至链表的首位,即添加至head之后.
	 * 
	 * @param o
	 */
	public void addFirst(Object o) {
		addAfter(new Node(o), head);
	}

	/**
	 * 将新节点插入至已知的节点的前一个.
	 * 
	 * @param newNode
	 *            待添加的节点
	 * @param node
	 *            指定已知的节点
	 */
	private void addBefore(Node newNode, Node node) {
		// TODO Auto-generated method stub
		newNode.setNext(node);
		newNode.setPrev(node.getPrev());
		newNode.getNext().setPrev(newNode);
		newNode.getPrev().setNext(newNode);
		size++;
	}

	/**
	 * 将新节点插入至已知的节点的后一个.
	 * 
	 * @param newNode
	 *            待添加的节点
	 * @param node
	 *            指定已知的节点
	 */
	private void addAfter(Node newNode, Node node) {
		newNode.setPrev(node);
		newNode.setNext(node.getNext());
		newNode.getPrev().setNext(newNode);
		newNode.getNext().setPrev(newNode);
		size++;
	}

	/**
	 * 链表打印,默认以next方式向后遍历 当然,我们也可以向前prev遍历,国际惯例是next
	 */
	public String toString() {
		StringBuffer ss = new StringBuffer("[");
		Node node = head;
		for (int i = 0; i < size; i++) {
			node = node.getNext();
			if (i > 0) {
				ss.append(",");
			}
			ss.append(node.getValue().toString());
		}
		ss.append("]");
		return ss.toString();
	}

	/**
	 * 添加节点至指点索引处,需要如下两部操作: 1> 找到该索引处的node. 2> 将新节点插入到所返回的node之后.
	 * 
	 * @param i
	 *            指定索引
	 * @param o
	 *            新节点
	 * @return boolean 返回值表示是否插入成功
	 */

	public boolean add(int i, Object o) {
		addBefore(new Node(o), getNodeByIndex(i));
		return true;
	}

	/**
	 * 这个的i,应该理解为链表的第几个节点,从1开始算,而不是直接的直接的索引.所以第i个元素的索引应该为i-1.
	 * 从head节点开始,不断向后遍历,找到i-1对应的节点.
	 * 
	 * @param i
	 *            第i-1个节点.
	 * @return 返回i-1位置的Node.
	 */
	private Node getNodeByIndex(int index) {
		Node node = head;
		if (index < 0 || index > size) {// 位置非法则抛出索引越界异常
			throw new IndexOutOfBoundsException();
		} else {
			for (int j = 0; j < index; j++) {
				node = node.getNext();
			}
		}
		return node;
	}

	/**
	 * 删除指定值为value的节点. 1> 找到该节点在链表中的位置. 2> 更新该节点前后节点的指向,并将自己的前后指向设置为null.
	 * 
	 * @param node
	 */
	private void removeNode(Node node) {
		node.getPrev().setNext(node.getNext());
		node.getNext().setPrev(node.getPrev());
		node.setNext(null);
		node.setPrev(null);
		size--;
	}
	/**
	 * @return the head
	 */
	public Node getHead() {
		return head;
	}
	/**
	 * @param head
	 *            the head to set
	 */
	public void setHead(Node head) {
		this.head = head;
	}
	/**
	 * @return the size
	 */
	public int getSize() {
		return size;
	}
	/**
	 * @param size
	 *            the size to set
	 */
	public void setSize(int size) {
		this.size = size;
	}

}

 

文件三:测试类。模仿的网上的例子，受网络限制，我找不到原出处了，So Sorry!

public class MyDoubleLinkedListTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		MyDoubleLinkedList dll = new MyDoubleLinkedList();
		
		//1. 给链表添加节点.
		dll.add("乔峰");
		dll.add("段誉");
		dll.add("虚竹");
		dll.add("慕容复");		
		System.out.println(dll);
		
		//2. 添加节点至链表尾端.
		dll.addLast("天山童姥");
		System.out.println(dll);
		
		//3. 添加节点至链表头部.
		dll.addFirst("扫地僧");
		System.out.println(dll);
		
		//4. 添加节点至指定位置:如"王雨嫣"插入至队列第4个.
		dll.add(4,"王语嫣");
		System.out.println(dll);
		
		//5. 删除指定位置的节点,如 删除第4个节点,即刚才添加的"王语嫣".
		dll.delete(4);
		System.out.println(dll);
		
		//6. 查询指定位置的节点数值.
		System.out.println(dll.get(4));
		
	}

}

 测试类执行结果:

[乔峰,段誉,虚竹,慕容复]

[乔峰,段誉,虚竹,慕容复,天山童姥]

[扫地僧,乔峰,段誉,虚竹,慕容复,天山童姥]

[扫地僧,乔峰,段誉,王语嫣,虚竹,慕容复,天山童姥]

[扫地僧,乔峰,段誉,虚竹,慕容复,天山童姥]

虚竹

 

基本功能模拟成功.