链表的实现

   链表是一种重要的数据结构，在程序设计中占有很重要的地位。链表包括单向链表，双向链表和循环链表。Java语言中的对象引用实际上是一个指针（本文中的指针均为概念上的意义，而非语言提供的数据类型），所以我们可以编写这样的类来实现链表中的结点。
class Node （双向链表）
　　{
　　Object data;
    Node previous;//指向上一个结点
　　Node next;//指向下一个结点
　　}
   将数据域定义成Object类是因为Object类是广义超类，任何类对象都可以给其赋值，增加了代码的通用性。为了使链表可以被访问还需要定义一个表头，表头必须包含指向第一个结点的指针和指向当前结点的指针。为了便于在链表尾部增加结点，还可以增加一指向链表尾部的指针，另外还可以用一个域来表示链表的大小，当调用者想得到链表的大小时，不必遍历整个链表。
链表的数据结构：
    我们可以用类List来实现链表结构，用变量Head、Tail、Length、Pointer来实现表头。存储当前结点的指针时有一定的技巧，Pointer并非存储指向当前结点的指针，而是存储指向它的前趋结点的指针,当其值为null时表示当前结点是第一个结点。那么为什么要这样做呢？这是因为当删除当前结点后仍需保证剩下的结点构成链表，如果Pointer指向当前结点，则会给操作带来很大困难。那么如何得到当前结点呢，我们定义了一个方法cursor(),返回值是指向当前结点的指针。类List还定义了一些方法来实现对链表的基本操作，通过运用这些基本操作我们可以对链表进行各种操作。例如reset()方法使第一个结点成为当前结点。insert(Object d)方法在当前结点前插入一个结点，并使其成为当前结点。remove()方法删除当前结点同时返回其内容，并使其后继结点成为当前结点，如果删除的是最后一个结点，则第一个结点变为当前结点。
链表类List的源代码如下：

　　import java.io.*;
　　public class List
　　{
　　/*用变量来实现表头*/
　　private Node Head=null;
　　private Node Tail=null;
　　private Node Pointer=null;
　　private int Length=0;
　　public void deleteAll()
　　/*清空整个链表*/
　　{
　　Head=null;
　　Tail=null;
　　Pointer=null;
　　Length=0;
　　}
　　public void reset()
　　/*链表复位，使第一个结点成为当前结点*/
　　{
　　Pointer=null;
　　}
　　public boolean isEmpty()
　　/*判断链表是否为空*/
　　{
　　return(Length==0);
　　}
　　public boolean isEnd()
　　/*判断当前结点是否为最后一个结点*/
　　{
　　if(Length==0)
　　　throw new java.lang.NullPointerException();
　　else if(Length==1)
　　　return true;
　　else
　　　return(cursor()==Tail);
　　}
　　public Object nextNode()
　　/*返回当前结点的下一个结点的值，并使其成为当前结点*/
　　{
　　if(Length==1)
　　　throw new java.util.NoSuchElementException();
　　else if(Length==0)
　　　throw new java.lang.NullPointerException();
　　else
　　{
　　　Node temp=cursor();
　　　Pointer=temp;
　　　if(temp!=Tail)
　　　　return(temp.next.data);
　　　else
　　　　throw new java.util.NoSuchElementException();
　　}
　　}
　　public Object currentNode()
　　/*返回当前结点的值*/
　　{
　　Node temp=cursor();
　　return temp.data;
　　}
　　
　　public void insert(Object d)
　　/*在当前结点前插入一个结点，并使其成为当前结点*/
　　{
　　Node e=new Node(d);
　　if(Length==0)
　　{
　　　Tail=e;
　　　Head=e;
　　}
　　else
　　{
　　　Node temp=cursor();
　　　e.next=temp;
　　　if(Pointer==null)
　　　　Head=e;
　　　else
　　　　Pointer.next=e;
　　}
　　Length＋＋;
　　}
　　public int size()
　　/*返回链表的大小*/
　　{
　　return (Length);
　　}
　　public Object remove()
　　/*将当前结点移出链表，下一个结点成为当前结点，如果移出的结点是最后一个结点，则第一个结点成为当前结点*/
　　{
　　Object temp;
　　if(Length==0)
　　　throw new java.util.NoSuchElementException();
　　else if(Length==1)
　　{
　　　temp=Head.data;
　　　deleteAll();
    }
练习：
package Link;
/**
* 节点接口
*
* 要求：
* 1.实现下边所有的方法
* 2.根据链表中存储的数据进行排序（比如学生根据学分）
* 3.单链表、双链表、循环链表都实现一遍
* 4.链表总结
*/
public interface NodeLinkedListInterface {

/**
* 添加节点的方法
*
* @param node新添加的节点对象
*/
public abstract void add(Node node);

/**
* 在指定索引位置添加新节点
* @param node要添加的新节点
* @param index指定的索引位置
*/
public abstract void add(Node node, int index);

/**
* 移除指定的节点
* @param node要被移除的节点对象
* @return 返回true和false，true表示移除成功，false表示移除失败
*/
public abstract boolean remove(Node node);

/**
* 移除指定所以位置的节点
* @param index指定要移除的节点索引
* @return 返回true和false，true表示移除成功，false表示移除失败
*/
public abstract boolean remove(int index);

/**
* 获取指定索引位置的节点对象
*
* @param index指定的索引位置
* @return 返回节点对象，如果index的范围超出size，则返回null.
*/
public abstract Node get(int index);

/**
* 获取双链表中存储的元素总数
*
* @return 返回size的值，如果为0则表示链表中没有节点
*/
public abstract int size();

}


package Link;
public class NodeLinkedList implements NodeLinkedListInterface {//接口
private int size=0;//节点总数
private Node root=null;//根节点
private Node last=null;//尾节点
@Override
public void add(Node node) {
if(null==root){
//让根节点和尾节点都指向新添加的节点
root=node;
last=node;
}else{
//向尾节点添加节点
last.setNext(node);
//将设为上一个节点
node.setPrevious(last);
last=node;
}
size++;
}

@Override
public void add(Node node, int index) {
if(size<index||index<0){
System.out.println("下标越界");
}else{
Node newnode=get(index);
if(index==0){
//如果链表没有结点
root=node;
}else{
//得到上一个结点
Node pnode=newnode.getPrevious();
//设置新的引用关系
pnode.setNext(node);
node.setPrevious(pnode);
}
//设置新的引用关系
node.setNext(newnode);
newnode.setPrevious(node);
}
size++;
}

@Override
public Node get(int index) {
//超出索引，返回null
if(index>=size||index<0){
return null;
}
//让node为根节点
Node node=root;
//遍历至索引位置
for(int i=0;i<index;i++){
//获取node节点的下一个
node=node.getNext();
}
return node;
}

@Override
public boolean remove(Node node) {
int I =0;
for(int i=0;i<size;i++){
Node nodenow = get(i);
if(nodenow==node){
I = i;
}

}
//得到当前索引位置的节点
Node nodenow = get(I);
//得到父节点
Node Fnode = nodenow.getPrevious();
//得到子节点
Node Cnode = nodenow.getNext();
if(Fnode==null){
        root=Cnode;

}else if(Cnode==null){
Fnode.setNext(null);
}else{
Fnode.setNext(Cnode);
Cnode.setPrevious(Fnode);

}
    size--;
return true;
}

@Override
public boolean remove(int index) {
if(index<0||index>=size){
return false;
}else{
//得到当前索引位置的结点
Node node=get(index);
//得到上一个结点
Node pnode=node.getPrevious();
//得到下一个结点
Node nnode=node.getNext();
if(pnode==null){
root=nnode;
}else if(nnode==null){
pnode.setNext(null);
}else{
pnode.setNext(nnode);
nnode.setPrevious(pnode);
}
size--;
return true;
}

}

@Override
public int size() {
return size;
}
}


package Link;
/**
* 节点类
* @author Sara
*
*/
public class Node {
//节点数据
private int data;
private Node next;
private Node previous;
public Node(){
}
public Node(int data){
this.data=data;
}
public Node(int data,Node next,Node previous){
this.data=data;
this.next=next;
this.previous=previous;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public Node getPrevious() {
return previous;
}
public void setPrevious(Node previous) {
this.previous = previous;
}

}


package Link;
import java.util.Random;
public class Manager {

/**
* @param args
*/
public static void main(String[] args) {
NodeLinkedListInterface nll = new NodeLinkedList();
Random rand = new Random();
for(int i=0;i<10;i++){
Node node = new Node(rand.nextInt(100));
nll.add(node);
}
Node node = new Node(89);
nll.add(node, 5);
for(int i=0;i<nll.size();i++){
if(i==5){
Node node1 = nll.get(i);
System.out.print("new "+node1.getData()+"   ");
}else
{
Node node1 = nll.get(i);
    System.out.print(node1.getData()+"   ");
     }
}
System.out.println(" ");
nll.remove(6);
for(int i=0;i<nll.size();i++){
if(i==6){
Node node1 = nll.get(i);
System.out.print("该处删除"+"     "+node1.getData()+"   ");
}else
{
Node node1 = nll.get(i);
    System.out.print(node1.getData()+"   ");
     }
}
System.out.println(" ");
System.out.println("移除的是第" + (6) + "个节点");
nll.remove(nll.get(5));
for (int i = 0; i < nll.size(); i++) {
Node node2 = nll.get(i);
System.out.print(node2.getData() + "   ");
}
for (int i = 1; i < nll.size(); i++) {
for (int j = i; j > 0; j--) {

if (nll.get(j).getData() < nll.get(j - 1).getData()) {
int temp = nll.get(j).getData();
nll.get(j).setData(nll.get(j - 1).getData());
nll.get(j - 1).setData(temp);
}
}

}
System.out.println("");
System.out.println("从小到大排序后的结果为：");
for (int k = 0; k < nll.size(); k++) {
Node nodex = nll.get(k);
System.out.print(nodex.getData()+"   ");
}
}
}