Java双向链表的实现

学过数据结构的应该对双向链表比较熟悉，但如果用java语言是怎么来实现的呢？本节是来讨论如何用java语言来实现链表，主要谈谈对双向链表的理解。

链表其实是一种非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接来实现的。链表由一系列的结点组成，结点是由存储数据元素的数据域和存储结点地址的指针域。对于单链表而言，结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。但当我们对单链表进行操作时，有时你要对某个结点前面的一个结点进行操作时，又必须从表头重新查找（这是由单链表的结构所造成的），这样接相当麻烦，为了解决这个问题，从而提出了双向链表。双向链表，结点包含一个存储数据元素的数据域，还有两个指针域，一个存储子结点地址，另一个存储父结点地址。
为了说明这些问题，我们先自定义一个双向链表：

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;
	}
}

再来对这个链表进行测试：

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();
		}
	}
}

转载请注明来源：Java双向链表的实现

本文链接地址：http://www.yuguoxy.com/geekhome/?p=195