Java双向链表的实现

学过数据结构的人对双向链表都不陌生。用 Java 怎么实现？链表在内存里并不连续，逻辑顺序靠指针串起来。每个结点有数据域，还有指向其它结点的引用。

单链表只有后继。要对某个结点的前驱动手，只能从头再走一遍，很麻烦。双向链表多一个指向父结点的引用，前后都能走。

一、结点：数据 + 父指针 + 子指针

自定义结点 LinkNode：一个数据域 obj，两个指针域 child（后继）和 parent（前驱）。

package cn.链表;

/**

 * 双向链表

 * 

 * 

 */

public class LinkNode {

	private Object obj;

	private LinkNode child;

	private LinkNode parent;



	public LinkNode(Object obj) {

		this.obj = obj;

	}



	// 定义方法

	public Object getObj() {

		return obj;

	}



	public void setObj(Object obj) {

		this.obj = obj;

	}



	public LinkNode getChild() {

		return child;

	}



	public void setChild(LinkNode child) {

		this.child = child;

	}



	public LinkNode getParent() {

		return parent;

	}



	public void setParent(LinkNode parent) {

		this.parent = parent;

	}

}

二、链表操作：增删改查与双向遍历

测试类 LinkListTest 维护头结点 front 和尾结点 last。提供：尾插、按位置插、按位置删、按位置取、更新、求长度、从头打印、从某下标向前再向后打印。

package cn.链表;

/**

 * 双向链表的测试

 * 

 * @author Administrator

 * 

 */

public class LinkListTest {

	private static LinkNode front = null;

	private LinkNode last = front;



	public static void main(String args[]) {

		LinkListTest list = new LinkListTest();

		list.add("头结点");

		for (int i = 0; i < 10; i++) {

			list.add("结点" + i);

		}

		// 测试指定位置下取得结点

		Object obj = list.getLinkNode(3).getObj();

		// 测试在指定位置插入元素

		list.add(3, "新来的元素");

		System.out.println("<><><><><><><>" + obj);

		list.printLinkNode(front);

		System.out.println("<><><><><><><><><><><><><><><><><><><><><");

		// list.remove(3);

		// list.printLinkNode(front);

		list.upDate(3, "值被改变的元素");

		list.printLinkNode(front);

		System.out.println("<><><><><><><><><><><><><><><><><><><><><");

		list.printLinkNode1(3);



	}



	/**

	 * 在链表的后面插入元素

	 * 

	 * @param obj

	 */

	public void add(Object obj) {

		// 根据给定的值创建结点

		LinkNode node = new LinkNode(obj);

		if (front == null) {

			// 如果链表为空的时候

			// front.setChild(node);

			// node.setParent(front);

			// 第一个结点也即是最后一个结点

			front = node;

			last = front;

			// System.out.println(front.getObj());

		} else {

			// 新插入的结点为最后一个结点

			last.setChild(node);

			node.setParent(last);

			last = node;

		}

	}



	/**

	 * 在指定位置插入元素

	 * 

	 * @param index

	 * @param obj

	 */

	public void add(int index, Object obj) {

		// 先创建结点

		LinkNode node = new LinkNode(obj);

		// 判断传入的下标

		if (index < 0 || index > size()) {

			throw new RuntimeException("下标越界：size：" + size() + "index：" + index);

		} else {

			// 传入的下标符合要求

			if (front == null) {

				// 如果链表为空的时候

				front = node;

				last = front;

			} else if (index == size()) {

				add(node);

			} else {

				// 链表不为空,取得当前下标的结点

				LinkNode nownode = getLinkNode(index);

				// 得到父结点

				LinkNode fnode = nownode.getParent();

				// 重新定义新的引用关系

				fnode.setChild(node);

				node.setParent(fnode);



				node.setChild(nownode);

				nownode.setParent(node);

			}

		}

	}



	/**

	 * 根据下标，删除当前的结点

	 * 

	 * @param index

	 */

	public void remove(int index) {

		if (index < 0 || index > size()) {

			throw new RuntimeException("下标越界：size：" + size() + "index：" + index);

		} else {

			// 传入的下标符合要求

			if (front == null) {

				// 如果链表为空的时候

				System.out.println("链表为空，不能删除元素啦！！！");

			} else {

				// 链表不为空,取得当前下标的结点

				LinkNode nownode = getLinkNode(index);

				// 得到父结点

				LinkNode fnode = nownode.getParent();

				// 得到父结点

				LinkNode cnode = nownode.getChild();

				// 重新定义新的引用关系

				fnode.setChild(cnode);

				cnode.setParent(fnode);

			}

		}

	}



	/**

	 * 根据下标取得当前的结点

	 * 

	 * @param index

	 *            下标值

	 * @return

	 */

	public LinkNode getLinkNode(int index) {

		// 判断传入的下标

		if (index < 0 || index > size()) {

			throw new RuntimeException("下标越界：size：" + size() + "index：" + index);

		} else {

			// 先取得头结点

			LinkNode node = front;

			int i = 0;

			while (i < index) {

				i++;

				node = node.getChild();

			}

			return node;

		}

	}



	/**

	 * 在指定的位置，更新该结点，结点的值为obj

	 * 

	 * @param index

	 * @param obj

	 *            更改的结点的值

	 */

	public void upDate(int index, Object obj) {

		if (index < 0 || index > size()) {

			throw new RuntimeException("下标越界：size：" + size() + "index：" + index);

		} else {

			// 传入的下标符合要求

			if (front == null) {

				// 如果链表为空的时候

				System.out.println("链表为空，不能更新元素啦！！！");

			} else {

				// 链表不为空,取得当前下标的结点

				LinkNode nownode = getLinkNode(index);

				// 给结点重新赋值

				nownode.setObj(obj);

			}

		}

	}



	/**

	 * 得到链表的长度

	 * 

	 * @return

	 */

	public int size() {

		if (front == null) {

			// 链表为空

			return 0;

		} else {

			// 不为空

			LinkNode node = front;

			int count = 0;

			while (node != null) {

				count++;

				node = node.getChild();

			}

			return count;

		}

	}



	/**

	 * 打印链表

	 * 

	 * @param node

	 *            传入链表的头结点

	 */

	public void printLinkNode(LinkNode node) {

		if (front == null) {

			System.out.println("此链表为空！！！");

		} else {

			// 先取得头结点

			LinkNode n = front;

			// 遍历链表

			while (n != null) {

				Object obj = n.getObj();

				System.out.println(obj);

				n = n.getChild();

			}

		}

	}



	/**

	 * 根据指定的位置来前后遍历

	 * 

	 * @param index

	 */

	public void printLinkNode1(int index) {

		if (index < 0 || index > size()) {

			throw new RuntimeException("下标越界：size：" + size() + "index：" + index);

		}



		LinkNode nownode = getLinkNode(index);

		LinkNode cnode = nownode.getChild();

		int i = index;

		// 往前遍历

		while (nownode != null && i >= 0) {

			Object obj = nownode.getObj();

			System.out.println(obj);

			i--;

			nownode = nownode.getParent();

		}

		nownode = getLinkNode(index);

		// 往后遍历

		while (nownode != null && i < size()) {

			Object obj = nownode.getObj();

			System.out.println(obj);

			i++;

			nownode = nownode.getChild();

		}

	}

}

main 里先加头结点再加 0～9 共十个结点，取下标 3 的数据，再在 3 号位插入「新来的元素」，打印一遍后把 3 号位改成「值被改变的元素」，最后从下标 3 做双向遍历。remove 被注释掉了，需要时可打开。

一句话总结：双向链表多付一个父指针，换来从任意结点向前走；插入删除只改四条引用，查找仍要从头数到 index。