正文
简述：链表由结点构成，结点有数值和指针，本文采用带头结点的链表进行演示！！！
注：后继节点的地址(指针)指向后继节点的数值
首先创建一个Node节点的类
package cn.itcast.huahai.node; public class Node { public Object data; public Node next; //无参构造方法 构建首结点 public Node() { this(null,null); } //有参构造方法 public Node(Object data,Node next) { this.data=data; this.next=next; } //有参构造方法 新建节点便于插入 public Node(Object data) { this(data,null); } }
注：采用接口的方式去创建Node的方法
package cn.itcast.huahai.data; public interface IList { public void clear();//置空 public boolean isEmpty();//判断是否为空 public void insert(int i,Object x)throws Exception;//插入 public void remove(int i)throws Exception;//移出 public Object get(int i)throws Exception;//获取 public void display();//显示、打印 public int length();//长度 public int indexOf(Object x);//查找 }
实现这些接口里面的方法
1.初始化Node
package cn.itcast.huahai.node; import java.util.Scanner; /** * @author Administrator * * 头结点的链表 * */ class LinkList implements IList{ Node head; //头结点 //创建对象 public LinkList() { head=new Node(); } }
1.clear()
public void clear() { head.next=null; head.data=null; }
2.length()
public int length() { Node p=head.next; int length=0; while(p!=null) { length++; p=p.next; } return length; }
3.isEmpty():
//判断为头结点是否为空 @Override public boolean isEmpty() { return head.next==null;//判断首节点为空 }
4.insert()
//有头结点的链表的插入 @Override public void insert(int i, Object x) throws Exception { Node p=head; //定义头指针 //在'1'位置插入 //定义一个计数器 j int j=-1; while(p!=null&& j<i-1) {//i-1得到插入的结点的前驱结点的位置 //j可以得到插入的结点的前驱结点的指针所在位置 j++; p=p.next; } //尾结点的后续节点为null //当j>i-1时， if(p==null||j>i-1) { throw new Exception("没有合适位置"); } //在'0'位置插入，要插入的结点的前驱节点指针为head //创建新的结点 Node s=new Node(x); //将s的后续指针指向下一个结点 s.next=p.next; //将前驱结点的后续指针指向s p.next=s; }
5.remove()
//有头结点的链表的删除 //移出比尾结点的小标还大的节点 尾结点已经为空 @Override public void remove(int i) throws Exception { Node p=head; int j=-1; while(j<i-1&&p.next!=null) { j++; p=p.next; } if(j>i-1||p.next==null) { throw new Exception("位置不存在"); } p.next=p.next.next; }
6.get()
public Object get(int i) throws Exception { Node p=head.next; int j=0; while(p!=null&&j<i) { j++; p=p.next; } if(p==null&&j>i) { throw new Exception("不存在"); } return p.data; }
7.indexOf()
//根据i的元素确定长度 @Override public int indexOf(Object x) { Node p=head.next; int j=0; //p的后继节点指向0 while(p!=null&&!p.data.equals(x)) { j++; p=p.next; } if(p!=null) return j; else return -1; }
8.display()
public void display() { // TODO Auto-generated method stub Node node=head.next; while(node!=null) { System.out.print(node.data+" "); node=node.next; } System.out.println(); }
如果能解决您的疑惑，我将不胜荣幸！！！
