链表总结

链表总结：
链表是一种物理单元上非连续非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针域连接次序实现的。链表是由节点构成的，而节点
包括两个部分，数据域和指针域。数据域用来存储数据元素，指针域用来指向下一个节点。
链表分为三种： 单向链表，双向链表，循环链表。java中没有指针的概念，但可以引用对象，下面是对链表的操作。
单向链表的建立：
首先要创建一个链表的节点类：
public class LinkNode{
private Object obj;     //链表中存储的数据
private LinkNode next; //对下一个节点的引用

private Node next;
/**
* 构造方法,在创建对象时就传入节点中的对象
*/
public Node(Object obj){
this.obj=obj;
}
/**
* 设置当前节点
*/
public void setObj(Object obj){
this.obj=obj;
}
/**
* 得到当前节点
*/
public Object getObj(){
return obj;
}
/**
* 设置下一个节点
*/
public void setNext(Node next){
this.next=next;
}
/**
* 得到下一个节点
*/
public Node getNext(){
return next;
}
}
有了节点类，下面就可以建立链表了。首先要在链表上加节点。
public void add(Object obj){
//创建节点
LinkNode node = new LinkNode (obj);
if(front==null){
front=node;
last=node;
}else{
last.setNext(node);
last=node;
}
}
然后是输出链表元素
public void printlink(){
if(front==null){
System.out.println("链表为空，不能输出");
}else{
LinkNode node = front;
while(node!=null){
System.out.println(node.getObj());
node = node.getNext();
}
}
}
然后是主函数
public class LinkList{
public static LinkNode front = null; // 第一个节点
public LinkNode last = null; // 最后一个节点
public static void main(String []args){
LinkList list = new LinkList();
list.add("根");
list.add("aa");
list.add("bb");
list.add("cc");
list.printlist();
}
}
双向链表的建立：
双向链表的节点的建立和单向链表是相同的，只不过多了一个指针域，用来指向父节点。
public class LinkNode{
//节点内的数据对象
private Object obj;
//对下一个节点的引用
private LinkNode child;
//对上一个节点的引用
private LinkNode parent;
/**
* 构造方法
*/
public LinkNode(Object obj){
this.obj=obj;
}
/**
* 设置当前的节点
*/
public void setObj(Object obj){
this.obj=obj;
}
/**
* 得到当前的节点
*/
public Object getObj(){
return obj;
}
/**
* 设置下一个节点
*/
public void setchild(LinkNode child){
this.child=child;
}
/**
* 得到下一个节点
*/
public LinkNode getchild(){
return child;
}
/**
* 设置上一个节点
*/
public void setParent(LinkNode parent){
this.parent=parent;
}
/**
* 得到上一个节点
*/
public LinkNode getParent(){
return parent;
}
}
双向链表的输出元素操作和单向链表相同，在这主要写一下双向链表的增加，插入，删除，更改的操作。
双向链表增加元素，节点的指针域不只是指向后一个节点，也要指向上一个节点。
public void add(Object obj){
LinkNode node = new LinkNode(obj);
if(front==null){
front = node;
last = node;
}else{
last.setchild(node);
node.setParent(last);
last = node;
}
}
现在讨论根据给定下标取出结点的方法，首先要判断给定的下标是否合法，如果不合法，则抛出异常，否则先取得头结点，根据头结点
去得到指定的结点，具体代码如下所示：
public LinkNode getLinkNode(int index) {
if (index < 0 || index > this.getlength()) {
throw new java.lang.RuntimeException("下标越界：" + index + ",size: "
+ this.getlength());
}else{
int count=0;
LinkNode node = front;
while(count!=index){
node=node.getchild();
count++;
}
return node;
}
}
然后要得到链表的结点的个数，将链表的头结点给node，对node进行判断，如果为空，则返回0；如果不为空，则定义一个计数器，根
据头结点依次取下一个节点，以得到结点的个数，代码如下：
/**
* 得到链表长度
*/
public int getlength() {
LinkNode node = front;
int count = 0;
while(node!=null){
node = node.getchild();
count++;
}
return count;
}
要在链表中的指定位置插入结点，首先要定义一个插入结点的方法，将指定位置和要插入的结点的数据域作为参数传入，然后在判断给定的下标
是否合法，如果不合法，则抛出异常；如果合法，则要先判断链表是否为空，如果为空，则将新结点作为头结点，如果指定的位置为末尾，则调用上面
增加结点的方法，否则根据上面去链表中元素的方法，得到指定的结点，然后再重新设定引用关系就可以了，具体操作如下:
public void insert(int index,Object obj){
if (index < 0 || index > this.getlength()) {
throw new java.lang.RuntimeException("下标越界：" + index + ",size: "
+ this.getlength());
}else{
LinkNode node = this.getLinkNode(index);
LinkNode newnode = new LinkNode(obj);
if(front = null){
front = newnode;
last = newnode;
}else{
LinkNode fnode = node.getParent();
fnode.setchild(newnode);
newnode.setParent(fnode);
}
newnode.setchile(node);
node.setParent(newnode);
}
}
要删除链表中的指定结点，方法和上面差不多，首先要判断给定的下标是否合理，然后在判断链表是否为空，如果不为空，则要根据上面取得
链表中元素的方法，先取得当前结点和该节点的前驱与后继，再重新定义前驱与后继的引用关系就行了，具体代码如下:
public void delete(int index) {
if (index < 0 || index > this.getlength()) {
throw new java.lang.RuntimeException("下标越界：" + index + ",size: "
+ this.getlength());
} else {
// 得到当前索引所指的节点
LinkNode node = this.getLinkNode(index);
// 得到当前节点的父节点
LinkNode fnode = node.getParent();
// 得到当前节点的子节点
LinkNode cnode = node.getchild();
if (fnode == null) {
front = cnode;
} else if (cnode == null) {
fnode.setchild(null);
} else {
fnode.setchild(cnode);
cnode.setParent(fnode);
}

}
}
然后是更改链表元素的方法，首先找到要更改的元素位置，然后对其数据进行修改。
/**
* 修改链表对象
*/
public void Updata(int index, Object obj) {
if (index < 0 || index > this.getlength()) {
throw new java.lang.RuntimeException("下标越界：" + index + ",size: "
+ this.getlength());
} else {
// 得到当前的节点
LinkNode node = this.getLinkNode(index);
node.setObj(obj);
}
}
双向链表的操作大概就是这些，下面是主函数。
public class DoubleLink {
public static LinkNode front = null; // 第一个节点
public LinkNode last = null; // 最后一个节点

public static void main(String[] args) {
DoubleLink list = new DoubleLink();
list.add(3);
list.add(2);
list.add(4);
list.add(6);
list.add(7);
list.add(1);
list.printlink();
System.out.println("排序后的链表为：");
list.order();
list.printlink();
System.out.println("链表长度：" + list.getlength());
System.out.println("<><><><><><><><><><><><><><>");
// 插入节点
list.insert(0, 2);
list.printlink();
System.out.println("链表长度：" + list.getlength());
System.out.println("<><><><><><><><><><><><><><>");
// 删除节点
list.delete(6);
list.printlink();
System.out.println("链表长度：" + list.getlength());
System.out.println("<><><><><><><><><><><><><><>");
}
下面是输出结果：
3
2
4
6
7
1
排序后的链表为：
1
2
3
4
6
7
链表长度：6
<><><><><><><><><><><><><><>
2
1
2
3
4
6
7
链表长度：7
<><><><><><><><><><><><><><>
2
1
2
3
4
6
链表长度：6
<><><><><><><><><><><><><><>