链表总结

1.链表总结
链表是是一种物理存储单元上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针接次实现的。
注：java中用引用来代替指针的使用
链表包含两部分：
一是数据域，二是：引用（指针域）。
链表的种类
1.单向链表
2.双向链表
3.循环链表
注：单向链表与循环链表最为相似
单向链表：数据域+引用
双向链表：数据域+两个引用（一个指上一个节点，一个指下一个节点）
循环链表：数据域+引用（最后一个节点的引用指向头节点）
以下是链表的简单操作：
单向链表：
/**
* 创建节点对象
* @author admin
*
*/
public class LinkNode {
//节点人的数据对象
private Object obj;
//下一个节点对象的易用
private  LinkNode next;
//创建节点对象的时候传入节点的数据对象
public LinkNode(Object obj){
this.obj=obj;
}
//设置得到对象的方法
public void setObj(Object obj){
this.obj= obj;
}
//设置获取对象的方法
public Object getObj(){
return obj;
}
//设置 下一个节点的地址
public void setNext(LinkNode next){
this.next  = next;
}
//设置获取下一个节点坐标的方法
public LinkNode getNext(){
return next;
}

}








/**
*单向链表
*/
public class LinkList {
private LinkNode root;

/**
*主函数
*/
public static void main(String[] args) {
//实例化对象
LinkList list = new LinkList();
//创建链表
LinkNode root =  list.createLink() ;
//遍历
list.printLinkList(list.root);

}
//手工创建链表
public LinkNode createLink(){
String s = "根节点";
root = new LinkNode(s);
LinkNode n1 = new LinkNode("一节点");
LinkNode n2 = new LinkNode("二节点");
LinkNode n3 = new LinkNode("三节点");
LinkNode n4 = new LinkNode("四节点");
root.setNext(n1);
n1.setNext(n2);
n2.setNext(n3);
n3.setNext(n4);

//
return root;

}
/**
* 遍历链表的的方法
* @param root 链表的根节点
*/
public void printLinkList(LinkNode root){
if(null!=root){
Object date = root.getObj();
System.out.println(date);
LinkNode temp = root.getNext();
printLinkList(temp);
}
}

}
双向链表：
节点类对象
public class LinkNode2 {
     //节点人的数据对象
private Object obj;
//下一个节点对象的易用
private  LinkNode2 child;
//对下一个节点的引用
private LinkNode2 parent;
//创建节点对象的时候传入节点的数据对象
public LinkNode2(Object obj){
this.obj=obj;
}
//设置得到对象的方法
public void setObj(Object obj){
this.obj= obj;
}
//设置获取对象的方法
public Object getObj(){
return obj;
}
//设置 下一个节点的地址
public void setChild(LinkNode2 child){
this.child  = child;
}
//设置获取下一个节点坐标的方法
public LinkNode2 getChild(){
return child;
}
//设置 上一个节点的地址
public void setParent(LinkNode2 parent){
this.parent  = parent;
}
//设置获取上一个节点坐标的方法
public LinkNode2 getParent(){
return parent;
}

}
简单双向链表的简单操作

/**
* 插入节点的方法
*/
public void add(Object obj){
//创建一个新的节点
LinkNode2 node = new LinkNode2(obj);
if(null==front){//如果链表为空
front = node;
last  = front;

}else{
last.setChild(node);

node.setParent(last);
last=node;
}


}
获取链表的长度
public int getLenght(){
//定义一个计数器
int lenght=0;
//如果链表为空
if(front==null){
return lenght;
}
//如果链表不为空，得到点一个节点的下一个节点
LinkNode2 node = front.getChild();
while(node!=null){
lenght++;
node = node.getChild();

}
return lenght+1;
}
根据索引取出节点
public LinkNode2 getLinkNode2(int index){
if(this.getLenght()<index||index<0){
throw new java.lang.RuntimeException("下标越界");
}else{
int num=0;
LinkNode2 node = front;
while(num!=index){
node=node.getChild();
num++;


}
return node;
}

}
在指定位置索引下插入节点
public void insertIndexObj(int index,Object obj ){
//判断
if(this.getLenght()<index||index<0){
throw new java.lang.RuntimeException("下标越界");
}else{
//实例化一个节点
LinkNode2 newnode = new LinkNode2(obj);
//得到当前的索引位置
LinkNode2 node = this.getLinkNode2(index);
if(index==0){//如果链表没有节点
front=newnode;
}else{
//得到父节点
LinkNode2 fNode = node.getParent();
//设置新的引用关系
fNode.setChild(newnode);
newnode.setParent(fNode);

}


//设置新的引用关系
newnode.setChild(node);
node.setParent(newnode);
}


}