[数据结构与算法]双链表的实现

先前只要好好看过我前面写的单链表步骤实现后面的双链表代码不难，就当是给读者一个小练习吧，我就直接上代码了就不一一介绍了。

package Test14;
class Node{
    public int data;
    public Node next;
    public Node prev;

    public Node(int data) {
        this.data = data;
    }
}

public class Test03 {
    public Node head;
    public Node last;

    //头插法
    public void addFirst(int data) {
        Node node=new Node(data);
        if(this.head!=null){
            head.prev=node;
            node.next=head;
            head=node;
        }else{
            head=node;
            last=node;
        }
    }
    //尾插法
    public void addLast(int data) {
        Node node=new Node(data);
        if(this.head!=null){
            last.next=node;
            node.prev=last;
            last=node;
        }else{
            head=node;
            last=node;
        }
    }
    //任意位置插入,第一个数据节点为0号下标
    public Node findnode(int index){
        Node cur=this.head;
        while (index-1!=0){
            cur=cur.next;
            index--;
        }
        return cur;
    }
    public void addIndex(int index,int data) {
        if(index<0||index>size()){
            System.out.println("输入的数有问题");
            return;
        }

        if(index==0){
            addFirst(data);
            return;
        }
        if(index==size()){
            addLast(data);
            return;
        }

        Node node=new Node(data);
        Node cur=findnode(index);

        node.next=cur.next;
        node.prev=cur;
        cur.next.prev=node;
        cur.next=node;
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        if(this.head==null){return false;}
        Node cur=this.head;
        while (cur!=null){
            if(cur.data==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        Node cur=this.head;
        while (cur!=null){
            if(cur.data==key){
                if(cur==this.head){
                    this.head=this.head.next;
                    if(this.head==null){
                        this.last=null;
                    }else{
                        head.prev=null;
                    }
                }else{
                    if(cur.next==null){
                        cur.prev.next=null;
                        this.last=cur.prev;
                    }else {
                        cur.prev.next=cur.next;
                        cur.next.prev=cur.prev;
                    }
                }
                return;
            }else{
                cur=cur.next;
            }
        }
    }
    //删除所有值为key的节点
    public void removeAllKey(int key) {
        Node cur=this.head;
        while (cur!=null){
            if(cur.data==key){
                if(cur==this.head){
                    this.head=this.head.next;
                    if(this.head==null){
                        this.last=null;
                    }else{
                        head.prev=null;
                    }
                }else{
                    if(cur.next==null){
                        cur.prev.next=null;
                        this.last=cur.prev;
                    }else {
                        cur.prev.next=cur.next;
                        cur.next.prev=cur.prev;
                    }
                }
                cur=cur.next;
            }else{
                cur=cur.next;
            }
        }
    }
    //得到单链表的长度
    public int size() {
        if(this.head==null) {return -1;}
        Node cur=this.head;
        int count=0;
        while (cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }

    public void display() {
        Node cur=this.head;
        while (cur!=null){
            System.out.print(cur.data+" ");
            cur=cur.next;
        }
        System.out.println();
    }

    public void clear() {
        Node cur=this.head;
        while (cur!=null){
            Node curNext=cur.next;
            cur.next=null;
            cur.prev=null;
            cur=curNext;
        }
        this.head=null;
        this.last=null;
    }

    public static void main(String[] args) {
        Test03 test03=new Test03();
        test03.addFirst(1);
        test03.addFirst(2);
        test03.addLast(3);
        test03.addLast(2);
        test03.addIndex(2,10);
        test03.display();
        System.out.println("============================");
        test03.removeAllKey(2);
        test03.display();
        System.out.println(test03.size());
        System.out.println(test03.contains(10));
        test03.clear();
        test03.display();
    }
}

可以看到这说明你吧这个认真看完了，加油吧年轻人！！！