【数据结构】单链表的实现（Java语言描述）

单链表是有一个个结点组成的有序表。以下定义单链表的结点类和单链表类来描述单链表。 1、单链表结点类Node声明如下：

//自引用类 public class Node<T> { public T data; public Node<T> next; public Node(T data,Node<T>next){ this.data=data; this.next=next; } public Node(){ this(null,null); } }

2、单链表类的声明（带头结点） 这里写了三种构造方法，适用于不同条件。

public class SinglyLinkedList<T> implements LList<T> { //构造函数，构造空链表 public SinglyLinkedList(){ this.head=new Node<T>(); } //构造方法，根据数组构造链表 public SinglyLinkedList( T [] element){ this(); Node<T> rear=this.head; for(int i=0;i<element.length;i++) { rear.next=new Node<T>(element[i],null); rear=rear.next; } } //根据一个单链表来构造另一个单链表，深拷贝,仅复制结点，没有复元 //素对象，导致两个链表的结点公用元素对象 public SinglyLinkedList(SinglyLinkedList<T>list){ this(); Node<T>p=list.head.next; Node<T>rear=this.head.next; while(p!=null){ rear.next=new Node<T>(p.data,null); rear=rear.next; p=p.next; } } }

3、判断是否是空链表

public boolean isEmpty() { // TODO Auto-generated method stub return this.head.next==null; }

4、得到链表的长度

public int length() { // TODO Auto-generated method stub int i=0; Node<T>p=this.head.next; //判断p是否是最后一个结点，循环结束后p=null while(p!=null){ i++;; p=p.next; } return i; }

5、得到某个结点

public T get(int i) { // TODO Auto-generated method stub if(i>=0){ Node<T> p=this.head.next; for(int j=0;j<i&& p!=null;j++){ p=p.next; } if(p!=null){ return p.data; } } return null; }

6、设置某个结点的值

public void set(int i, T x) { // TODO Auto-generated method stub if(x==null){ return; } if(i>=0){ Node<T> p=this.head.next; for(int j=0;j<i&&p!=null;j++){ p=p.next; } if(p!=null){ p.data=x; } } else throw new IndexOutOfBoundsException(i+""); }

7、根据索引插入

public void insert(int i, T x) { // TODO Auto-generated method stub if(x==null) return; if(i>=0) { Node<T>p=this.head.next; //循环结束后p是最后一个结点或者是第i个结点 for(int j=0;j<i&&p!=null;j++){ p=p.next; } p.next=new Node<T>(x,p.next); } }

8、追加

public void append(int i, T x) { // TODO Auto-generated method stub insert(Integer.MAX_VALUE,x); }

9、删除结点

public T remove(int i) { // TODO Auto-generated method stub if(i>=0) { Node<T>p=this.head.next; //p是倒数第二个节点的时候结束 for(int j=0;j<i&&p!=null;j++){ //此时p是最后一个结点或者是第i个结点 p=p.next; } //如果不是最后一个结点 if(p.next!=null){ T old=p.next.data; p.next=p.next.next; return old; } } return null; }

10、清除链表

public void removeAll() { // TODO Auto-generated method stub this.head.next=null; }

11、查找

public T search(T key) { // TODO Auto-generated method stub if(key==null) { return null; } Node <T>p=this.head.next; while(p!=null){ if(p.data.equals(key)){ return p.data; } p=p.next; } return null; }

12、判等

public boolean equals(Object obj){ if(obj==this){ return true; } if(!(obj instanceof SinglyLinkedList)){ return false; } Node<T> p=this.head.next; Node<T> q=((SinglyLinkedList<T>)obj).head.next; while(p!=null && q!=null&& p.data.equals(q.data)){ p=p.next; q=q.next; } return p==null&&q==null; }

13、把链表的所有结点的值转化为字符串(A,B,C,D,E)

public String toString(){ String str="("; Node<T> p=this.head.next; while(p!=null){ str+=p.data.toString(); //如果不是最后一个，则加一个逗号 if(p.next!=null){ str+=","; } p=p.next; } return str+=")"; }

14、应用举例之翻转链表

public class Reverse { public static void main(String[] args) { // TODO Auto-generated method stub String []value={"A","B","C","D","E"}; SinglyLinkedList<String> list=new SinglyLinkedList<String>(value); System.out.println("list是"+list.toString()); reverse(list); System.out.println("翻转后的list是"+list.toString()); } //将单链表逆转，泛型方法，返回值类型前声明类型参数T public static <T> void reverse(SinglyLinkedList <T>list) { Node<T>p=list.head.next; Node<T>succ=null; Node<T>front=null; while(!(p==null)){ succ=p.next; p.next=front; //通过这种方式来找p的前驱结点，以及将p后移 //循环结束后front是未翻转的最后一个结点，p=null front=p; p=succ; } //将front作为头结点 list.head.next=front; } }

15、排序单链表（升序）声明 排序单链表是指插入结点的时候按照data域的大小进行排序。在一个排序单链表中插入一个（data）值域为x的结点，插入位置有x值的大小决定，确定位置是查找过程，即从单链表的第一个结点开始，将x分别于每个结点的值域比较，一旦找到一个比x大的值的结点p,则将该结点插入p结点之前。此时应记住p的前驱结点front,将x插入在front结点之后。 按升序Dev单链表类SinglyLinkedList声明如下：类型参数T必须实现java.lang.Comparable接口，提供CompareTo方法支持对象比较大小。

public class SortedSinglyLinkedList<T extends Comparable<T>> extends SinglyLinkedList{ public SortedSinglyLinkedList(){ super(); } public SortedSinglyLinkedList( T [] element){ super(); if(element!=null){ for(int i=0;i<element.length;i++){ this.insert(element[i]); } } } public SortedSinglyLinkedList( SortedSinglyLinkedList<T>list){ super(list); }

16、插入

public void insert(T x){ if(x==null) return; //p从第一个结点开始 //找到p的前驱结点 Node<T>front=this.head; Node<T>p=front.next; //p!=null p=p.next; 保证循环结束后p是null， while(p!=null && p.data.compareTo(x)<0){ front=p; p=p.next; } front.next=new Node<T>(x,p); } public void insert(int i,T x){ throw new UnsupportedOperationException("insert(int i,T x)"); } public void append(T x){ throw new UnsupportedOperationException("append(T x)"); }

17、删除

//和父类的remove方法返回参数不同 public void remove(T x){ if(x==null) return; //找到p的前驱结点 Node<T>front=this.head; Node<T>p=front.next; //p!=null p=p.next; 保证循环结束后p是null， while(p!=null && p.data.compareTo(x)<0){ front=p; p=p.next; } if(p!=null &&p.data.compareTo(x)==0){ front.next=p.next; } }

18、循环单链表 循环单链表的头和尾接连，其声明如下：

public class CirleSinglyLinkedList<T> { public Node<T>head; //构造空循环链表 public CirleSinglyLinkedList(){ this.head=new Node<T>(); this.head.next=this.head; } //构造方法，根据数组构造链表 public CirleSinglyLinkedList( T [] element){ this(); Node<T> rear=this.head; for(int i=0;i<element.length;i++) { rear.next=new Node<T>(element[i],null); rear=rear.next; } //保证链表的尾结点的next是头结点 rear.next=this.head; }

19、toString方法

public String toString(){ int i=0; String str="("; Node<T> p=this.head.next; while(p!=this.head){ i++; str=str+p.data; System.out.println("str是"+str); //如果不是最后一个，则加一个逗号 if(p.next!=this.head){ str+=","; System.out.println("i是"+i); } p=p.next; } return str+=")"; }

循环单链表的其他方法和单链表的基本相同的，只是判断条件不同。

结点循环单链表单链表最后一个结点p.next=headp.next=null最后一个结点的nextp=this.headp=null