Java中自定义链表总结

在C/C++中可知链表是一种物理存储单元上非顺序的线性存储结构，链表是由结点组成的，结点包括两部分：一个是数据域，另一个是指针域，数据域存储数据元素，指针域指向下一个结点的地址，在Java中没有指针的概念，但是可以引用对象。这里总结自定义链表的操作。
链表分为三种：一种是单向链表，一种是双向链表，另外一种是循环链表。现在我们自己可以实现一个单向链表结构。首先要先定义一个链表的结点类，包括数据域和引用对象两个对象，以及对这两个对象的值的设置和得到值的方法。具体代码如下所示：
/**
* 创建结点
* @author lenovo
*
*/
public class LinkNode {

private Object obj;
private LinkNode node = null;

public LinkNode(Object obj){
this.obj = obj;
}


public Object getObj() {
return obj;
}

public void setObj(Object obj) {
this.obj = obj;
}

public LinkNode getNode() {
return node;
}

public void setNode(LinkNode node) {
this.node = node;
}


}

有了结点之后就可以创建链表了，首先在单向链表类里定义一个创建链表的方法，然后实例化结点对象，最后设置各个结点间的引用关系，代码如下所示;

/**
* 创建一个单向链表
* @return：返回根结点
*/
public LinkNode createLinkNode(){
//创建结点
LinkNode root = new LinkNode("根结点");
LinkNode node1 = new LinkNode("结点一");
LinkNode node2 = new LinkNode("结点二");
LinkNode node3 = new LinkNode("结点三");
LinkNode node4 = new LinkNode("结点四");

//构建链表
root.setNode(node1);
node1.setNode(node2);
node2.setNode(node3);
node3.setNode(node4);


return root;
}

然后再遍历链表遍历链表时，首先要取出结点的数据域和指向下一个结点的引用对象，然后再用递归法就可以将链表遍历了。具体代码如下所示：
/**
* 根据根结点遍历链表
* @param root：根结点
*/
public void print(LinkNode root){

Object n = root.getObj();
LinkNode node = root.getNode();

System.out.println(n);

if (node!=null){
//递归
print(node);
}

}

主函数为：

public static void main(String args[]){
Link link = new Link();
LinkNode root = link.createLinkNode();
link.print(root);

}
输出结果为：
根结点
结点一
结点二
结点三
结点四

现在来创建双向链表，双向链表的创建与单向链表的创建的一样的，只不过要再加一个指针域，设指向结点前驱用parent表示，后继用Child表示，则双向链表结点类为：
public class Node {

private Object obj;
private Node parent = null;
private Node child = null;

public Node(Object obj){
this.obj = obj;
}

public Object getObj() {
return obj;
}
public void setObj(Object obj) {
this.obj = obj;
}
public Node getParent() {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
public Node getChril() {
return child;
}
public void setChril(Node child) {
this.child = child;
}
}
创建双向链表的方法与单向链表的方法差不多，具体如下所示：
public void createLink(){
//创建结点
Node root = new Node("根结点");
Node node1 = new Node("结点一");
Node node2 = new Node("结点二");
Node node3 = new Node("结点三");
Node node4 = new Node("结点四");
Node node5 = new Node("结点五");
Node node6 = new Node("结点六");

//构建双向链表
root.setChril(node1);
node1.setParent(root);
node1.setChril(node2);
node2.setParent(node1);
node2.setChril(node3);
node3.setParent(node2);
node3.setChril(node4);
node4.setParent(node3);
node4.setChril(node5);
node5.setParent(node4);
node5.setChril(node6);
node6.setParent(node5);

}
对象双向链表的遍历与单向链表的遍历是一样的，不同的是单向链表必须要从头结点开始遍历，而双向链表可以从任一个结点开始遍历。
现在主要讨论对象双向链表的各种操作，比如增、删、改等，下面先来看在双向链表末尾添加结点的方法。首先定义双向链表的头结点和尾结点为：
private static Node Head = null;//头结点
private Node foot = Head;//尾结点

根据新结点的数据域创建一个新结点，所以将要增加的结点的数据域作为参数传入，然后再判断链表的头结点是否为空，如果为空，则将新结点作为头结点，如果不为空，则在尾结点后插入新结点，将新结点作为尾结点，具体代码如下所示：
/**
* 将结点添加到双向链表末尾
* @param obj：要添加的结点
*/
public void add(Object obj){
//创建一个新的结点
Node node = new Node(obj);

if (Head==null){//如果头结点为空
//将新的结点作为头结点
Head = node;
foot = Head;
}else {//头结点不为空
//建立新的引用关系，将新的结点作为尾结点
foot.setChril(node);
node.setParent(foot);
foot = node;

}

}
现在讨论根据给定下标取出结点的方法，首先要判断给定的下标是否合法，如果不合法，则抛出异常，否则先取得头结点，根据头结点去得到指定的结点，具体代码如下所示：
/**
* 得到指定下表的结点
* @param index
* @return
*/
public Node getNode(int index){

if (index<0||index>Size()){//判断指定的下标是否越界
throw new RuntimeException("下标越界："+index+",size:"+Size());
}else {
int num = 0;
//取得头结点
Node node = Head;
while(num<index){
node = node.getChril();
num++;
}

return node;

}

}

然后要得到链表的结点的个数，首先要判断链表是否为空，如果为空，则返回0；如果不为空，则定义一个计数器，根据头结点去遍历链表，以得到结点的个数，代码如下：
/**
* 计算链表中结点的个数
* @return
*/
public int Size(){
int count=0;
if (Head==null){//头结点为空
return 0;
}else{//头结点不为空
//取得头结点
Node node = Head;

while(node!=null){
count++;
node = node.getChril();
}

return count;
}

}

要在链表中的指定位置插入结点，首先要定义一个插入结点的方法，将指定位置和要插入的结点的数据域作为参数传入，然后在判断给定的下标是否合法，如果不合法，则抛出异常；如果合法，则要先判断链表是否为空，如果为空，则将新结点作为头结点，如果指定的位置为末尾，则调用上面增加结点的方法，否则根据上面去链表中元素的方法，得到指定的结点，然后再重新设定引用关系就可以了，具体操作如下:
/**
* 在指定位置插入结点
* @param index：插入的位置
* @param boj：要插入的结点
*/
public void add(int index,Object obj){

//创建新的结点
Node newNode = new Node(obj);
//得到该位置的结点
Node node = getNode(index);

if (index<0||index>Size()){//判断指定的下标是否越界
throw new RuntimeException("下标越界：size："+Size()+"index："+index);
}else {
if (Head==null){//头结点为空
//将新结点作为头结点
Head = newNode;
foot = Head;
}else if(index==Size()){
add(newNode);
}else{
//得到当前下标结点的前一个结点
Node LNode = node.getParent();

//建立新的引用关系
LNode.setChril(newNode);
newNode.setParent(LNode);

newNode.setChril(node);
node.setParent(newNode);


}

}

}

要删除链表中的指定结点，方法和上面差不多，首先要判断给定的下标是否合理，然后在判断链表是否为空，如果不为空，则要根据上面取得链表中元素的方法，先取得当前结点和该节点的前驱与后继，再重新定义前驱与后继的引用关系就行了，具体代码如下;
/**
* 删除链表指定位置的结点
* @param index:要删除结点的下标
*/
public void remove(int index){

if (index<0||index>Size()){//判断指定的下标是否越界
throw new RuntimeException("下标越界：size："+Size()+"index："+index);
}else {
if (Head==null){//如果链表为空
System.out.println("该链表为空！！");
}else {//链表不为空
//得到当前结点
Node node = getNode(index);
//得到父结点
Node fNode = node.getParent();
//得到子结点
Node cNode = node.getChril();

//重新设置新的引用关系
fNode.setChril(cNode);
cNode.setParent(fNode);

}

}
}

而要修改给定结点的方法如下所示：
/**
* 修改指定的结点的数据域
* @param index：指定的结点下标
* @param obj：要修改成的值
*/
public void upData(int index,Object obj){

if (index<0||index>Size()){//判断给定的下标是否越界
throw new RuntimeException("下标越界："+index+",size:"+Size());
}else {
if (Head==null){//如果链表为空
System.out.println("链表为空，不能修改！！");
}else {
//取得当前结点
Node node = getNode(index);
//修改该结点数据域
node.setObj(obj);
}
}
}

根据如下主函数运行上面的方法如下：
主函数：
public static void main(String args[]){
DulLink dl = new DulLink();
//dl.createLink();

dl.add("新来的");
for(int i=0;i<10;i++){
dl.add("结点"+i);
}

//测试指定位置下取得结点
Object obj=dl.getNode(3).getObj();
System.out.println("<><><><><><><>"+obj);
//测试在指定位置插入元素
dl.add(3, "新来的元素");
System.out.println("新来的元素:"+obj);
dl.print(Head);
System.out.println("<><><><><><><><><><><><><><><><><><><><><");
dl.remove(3);
dl.print(Head);
dl.upData(3, "值被改变的元素");
dl.print(Head);



}
运行结果：
<><><><><><><>结点2
新来的元素:结点2
新来的
结点0
结点1
新来的元素
结点2
结点3
结点4
结点5
结点6
结点7
结点8
结点9
<><><><><><><><><><><><><><><><><><><><><
新来的
结点0
结点1
结点2
结点3
结点4
结点5
结点6
结点7
结点8
结点9
新来的
结点0
结点1
值被改变的元素
结点3
结点4
结点5
结点6
结点7
结点8
结点9