Java双向链表的实现

周sir | 2015年4月12日 | Java集合框架与数据结构 | 0 条评论 | 1781

学过数据结构的应该对双向链表比较熟悉，但如果用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;
}
}[/java]
再来对这个链表进行测试：
[java]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]