链表

节点类

除双向链表外的节点类

/*
 * 节点类
 * params:指向下一个节点的成员变量
 *        其他的成员变量
 */
public class Link {
    public int num;
    public Link next;
    public Link(int num){
        this.num=num;
    }
}

双向链表的节点类

/*
 * 双向链表的节点类
 */
public class Link {
    public int num;
    public Link next;
    public Link previous;
    public Link(int num){
        this.num=num;
    }
}

单链表

每个节点只指向下一个节点
单链表的操作类

/*
 * 单链表的操作类
 */
public class SingleList {
    //头节点
    public Link first;
    //在链表的头部插入一个元素
    public void insertFirst(int num){
        Link link=new Link(num);
        link.next=first;
        first=link;
    }
    //在链表的头部删除一个元素
    public Link deleteFirst(){
        if(first==null){
            return null;
        }
        Link temp=first;
        first=first.next;
        return temp;
    }
    //遍历显示链表中的所有元素
    public void display(){
        Link current=first;
        while(current!=null){
            System.out.println(current.num+",");
            current=current.next;
        }
    }
    //根据变量查询指定元素节点
    public Link find(int num){
        Link current=first;
        while(current.num!=num){
            if(current.next==null){
                return null;
            }else{
                current=current.next;
            }
        }
        return current;
    }
    //根据指定变量删除节点
    public Link delete(int num){
        Link current=first;
        Link previous=null;
        while(current.num!=num){
            if(current.next==null){
                return null;
            }else{
                previous=current;
                current=current.next;
            }
        }
        if(current==first){
            first=first.next;
        }else{
            previous.next=current.next;
        }
        return current;
    }
}

双端链表

每个节点指向下一个节点，在链表的操作类中同时保留着对头结点和尾节点的引用

/*
 * 双端链表的操作类
 */
public class FirstLastList {
    public Link first;
    public Link last;
    //在头部插入一个节点
    public void insertFirst(int num){
        Link link=new Link(num);
        if(first==null){
            last=link;
        }
        link.next=first;
        first=link;
    }
    //在尾部插入一个节点
    public void insertLast(int num){
        Link link=new Link(num);
        if(first==null){
            first=link;
        }else{
            last.next=link;
        }
        last=link;
    }
    //在头部删除一个节点
    public Link deleteFirst(){
        if(first==null){
            return null;
        }
        Link temp=first;
        //判断删除这个节点后是否没有节点了,如果没有节点要把last置为null
        if(first.next==null){
            last=null;
        }
        first=first.next;
        return temp;
    }
    //遍历显示节点
    public void display(){
        Link current=first;
        while(current!=null){
            System.out.println(current.num);
            current=current.next;
        }
    }
}

1.双端链表不能直接从尾部删除元素，因为无法直接找到尾部前一个节点的引用。
2.双端链表按元素查找和删除节点的操作和单链表相同。

双向链表

1 双向链表，每一个节点即指向前一个节点，同时又指向下一个节点。
2 双向链表可以是双端链表也可以不是双端链表。

/*
 * 双向链表的操作类
 */
public class DoubleLinkList {
    public Link first;
    public Link last;
    //在头部插入一个节点
    public void insertFirst(int num){
        Link newLink=new Link(num);
        if(first==null){
            last=newLink;
        }else{
            first.previous=newLink;
        }
        newLink.next=first;
        first=newLink;
    }
    //在尾部插入一个节点
    public void insertLast(int num){
        Link newLink=new Link(num);
        if(first==null){
            first=newLink;
        }else{
            last.next=newLink;
            newLink.previous=last;
        }
        last=newLink;
    }
    //在某一个节点后面插入一个节点
    public void  insertAfter(int num,int targetNum){
        Link target=new Link(targetNum);
        Link current=find(num);
        if(current==null)
            return;
        if (current==last) {
            current.next=target;
            target.previous=current;
            last=target;
        }else{
            target.next=current.next;
            current.next.previous=target;
            current.next=target;
            target.previous=current;
        }
    }
    //删除第一个节点
    public Link deleteFirst(){
        if(first==null)
            return null;
        if(first.next==null){
            last=null;
        }else{
            first.next.previous=null;
        }
        Link temp=first;
        first=first.next;
        return temp;
    }
    //删除最后一个节点
    public Link deleteLast(){
        if(last==null){
            return null;
        }
        Link temp=last;
        if(last.previous==null){
            first=null;
        }else{
            last.previous.next=null;
        }
        last=last.previous;
        return temp;
    }
    //查询某一个节点
    public Link find(int num){
        Link current=first;
        while(current.num!=num){
            if(current.next==null){
                return null;
            }
            current=current.next;
        }
        return current;
    }
    //删除某一个节点
    public Link delete(int num){
        Link current=first;
        while(current.num!=num){
            if(current.next==null){
                return null;
            }
            current=current.next;
        }
        if(current==first){
            first.next.previous=null;
            first=current.next;
        }else if(current==last){
            current.previous.next=null;
            last=current.previous;
        }
        else{
            current.previous.next=current.next;
            current.next.previous=current.previous;
        }
        return current;
    }
    //从前向后遍历所有节点
    public void displayForward(){
        Link current=first;
        while(current!=null){
            System.out.println(current.num);
            current=current.next;
        }
    }
    //从后向前遍历所有节点
    public void displayBackword(){
        Link current=last;
        while(current!=null){
            System.out.println(current.num);
            current=current.previous;
        }
    }
}

有序链表

/*
 * 有序链表操作类
 */
public class SortedList {
    public Link first;
    //按从小到大的顺序向链表中插入元素
    public void insert(int num){
        Link link=new Link(num);
        Link current=first;
        Link previous=null;
        while(current!=null&&num>current.num){
            previous=current;
            current=current.next;
        }
        //previous==null说明没进循环，first为null或者插入的元素是目前最小的
        if(previous==null){
            first=link;
        }else{
            previous.next=link;
        }
        link.next=current;
    }
}

有序链表除了插入操作外，其他操作和单链表一致。