Java双向链表的实现

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

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

为了说明这些问题，我们先自定义一个双向链表：

package cn.链表;

/**

 * 双向链表

 * @author yl

 *

 */

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

}

}

}

下面也附了代码，自己可以拿去运行下。由于本人能力所限，如有什么问题，希望牛人指出。

<!--EndFragment-->