双向链表的模拟实现

一：什么是双向链表

1：什么是双向链表

双向链表，顾名思义，通过一个节点，可以知道它的前一个节点和后一个节点
如下图所示：
一个节点有三个域：
数值域：用来存放具体的数值；
prev域:用来存放当前节点的前一个节点的地址;
next域:用来存放当前节点的下一个节点的地址;

一个节点的实现:
当我们定义一个节点的时候,并不知道该节点的前一个节点和后一个节点是谁,所以构造方法中只有一个val参数.

  static class ListNode{
        public int val;//数值域
        public ListNode prev;//prev域
        public ListNode next;//next域
        public ListNode(int val) {
            this.val = val;
        }
    }

2:双向链表的结构

与单链表相似,双向链表也是由一个一个的节点组合的,但不同的是:单链表只有一个属性:头结点(head),而双向链表有两个属性:头结点(head)和尾节点(last).

 static class ListNode{
        public int val;
        public ListNode prev;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    ListNode head;
    ListNode last;

二：IList接口

public interface IList {
    //头插法
    void addFirst(int data);
    //尾插法
    void addLast(int data);
    //任意位置插入,第一个数据节点为0号下标
     void addIndex(int index,int data);
    //查找是否包含关键字key是否在单链表当中
     boolean contains(int key);
    //删除第一次出现关键字为key的节点
    void remove(int key);
    //删除所有值为key的节点
     void removeAllKey(int key);
    //得到双向链表的长度
    int size();
    //打印双向链表的数值域
    void display();
    //清空双向链表
     void clear();
}

在这里定义了一些双向链表的常用方法，下面我们将逐步实现这些方法。

三:方法的具体实现:

1:display()

思路:
遍历双向链表的每个节点,并打印每个节点的val域;

在这里有两点:
1:什么时候链表遍历完了?
当cur==null时,说明链表遍历完了
2:当前节点如何走向下一个节点:
cur=cur.next

    @Override
    public void display() {
        ListNode cur=head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();

    }

2:size()

思路
定义一个计数器:count,
还是遍历链表,每遍历一个节点,count++;
当链表遍历完了,返回的count值就是链表的长度

public int size() {
        ListNode cur=head;
        int count=0;
        while(cur!=null){
           count++;
            cur=cur.next;
        }
    return count;

3:contains()

思路:
遍历链表,并比较节点的值是否与key相同,相同返回true;不同cur=cur.next(遍历下一个节点)

public boolean contains(int key) {
        ListNode cur=head;
        while(cur!=null){
            if(cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }

4:addFirst(int data)

头插法:
顾名思义:就是把节点插入到头结点的位置处;
如果链表为空(head==null):插入的节点既是头结点又是尾结点,所以head和last都指向要插入的节点;
如果链表不为空:node.next=head;head.prev=node;head=node;

public void addFirst(int data) {
        ListNode node =new ListNode(data);
        if(head==null){
           head=node ;
            last=node ;

        }else{
            node.next = head;
            head.prev=node;
            head=node;

        }

    }

4:addLast(int data)

尾插法:
就是把新增加的元素放在最后一个节点
与头插法相似:
如果链表为空(head==null):插入的节点既是头结点又是尾结点,所以head和last都指向要插入的节点;
如果链表不为空:last.next=node;node.prev=last;last=node;

  public void addLast(int data) {
        ListNode node =new ListNode(data);
        if(head==null){
            head=node ;
            last=node ;

        }else{
           last.next=node;
           node.prev=last;
          last=node;
        }
    }

4:addIndex(int index, int data):

任意位置插入:
index表示要插入的位置,data表示要插入的数据
首先要判断index是否合法:index0代表头插;indexindexsize(),表示要插入的位置是最后一个节点,可以想象成链表是从0下标开始的(虽然链表没有下标这个概念),如果index不在这个范围内,就是不合法的.

如果index0;直接调用头插法addFirst(data)即可;
如果indexsize(),直接调用尾插法addLast(data)即可;
其他情况下:就代表在链表的中间位置插入:
首先我们定义一个cur节点:代表要插入的节点位置,但我们定义的时候,cur=head,那么我们就让cur走index步,比如:index=2;就让cur走到2位置处:具体实现代码:

 private ListNode findIndex(int index){
        ListNode cur =head;
        while(index!=0){
            cur=cur.next;
            index--;
        }
        return cur;
    }

当cur走到要增加节点的位置处:我们然后只需修改四个指向即可;
总结:当插入数据的时候,先绑定后面的,先修改next域,再修改prev域

public void addIndex(int index, int data) {
        if(index<0||index>size()){
            System.out.println("index错误"+index);
            return;
        }
        if(index==0){
            addFirst(data);
            return;
        }
        if(index==size()){
            addLast(data);
            return;
        }

        ListNode node = new ListNode(data);
        ListNode cur=findIndex(index);
        node.next=cur;
        cur.prev.next=node;
        node.prev=cur.prev;
        cur.prev=node;
    }
    private ListNode findIndex(int index){
        ListNode cur =head;
        while(index!=0){
            cur=cur.next;
            index--;
        }
        return cur;
    }

5:remove(int key)

删除第一次出现关键字为key的节点
思路:遍历链表的每个节点,当当前节点的val==key时,执行删除操作,删除完成返回即可,如果当前节点的val!=key,cur=cur.next,继续寻找即可.
1:如果要删除的节点是头结点:只需head.next.prev=null;head=head.next;
即可
2:如果要删除的节点是尾节点:
只需cur.prev.next=null;last=last.prev;即可

如果要删除的节点是在链表中间的数据:
比如:(如下图)删除34所在的节点
只需修改两个指向即可

  public void remove(int key) {
        ListNode cur=head;
        while(cur!=null){
            if(cur.val==key){
                if(cur==head){
                    head=head.next;
                    head.prev=null;
                } else if (cur==last) {
                    last=last.prev;
                    last.next=null;
                    //cur.prev.next=cur.next;
                }else{
                    cur.prev.next=cur.next;
                    cur.next.prev=cur.prev;

                }
                return;
            }else{
                cur = cur.next ;
            }
        }

    }

注意:当链表只有一个节点,且该节点的val=key,那么删除头节点的时候就会空指针异常:
因为 **head=head.next;**此时由于只有一个节点,那么head=null; 而head=null,这个语句:**head.prev=null;**就会报异常;
所以只有当head!=null时,才会执行这个语句
所以:当链表只有一个节点,且该节点的val=key,head=head.next;last=null;(唯一的节点也被删除了,last也要为空)
当链表除了要删除的该节点还有其他节点时:head=head.next;head.prev=null;
综上:

 public void remove(int key) {
        ListNode cur=head;
        while(cur!=null){
            if(cur.val==key){
                if(cur==head){
                    head=head.next;
                   if(head!=null){
                       head.prev=null;
                   }else{
                       last=null;
                   }

                } else if (cur==last) {
                    last=last.prev;
                    last.next=null;
                    //cur.prev.next=cur.next;
                }else{
                    cur.prev.next=cur.next;
                    cur.next.prev=cur.prev;

                }
                return;
            }else{
                cur = cur.next ;
            }
        }

    }

6:removeAllKey(int key)

删除所有值为key的节点
有了删除一个节点的基础,删除全部节点就很简单了;在删除某个节点后不要返回,让节点继续往后走就行了.

  public void removeAllKey(int key) {
        ListNode cur=head;
        while(cur!=null) {
            if (cur.val == key) {
                if (cur == head) {
                    head = head.next;
                    if (head != null) {
                        head.prev = null;
                    } else {
                        last = null;
                    }

                } else if (cur == last) {
                    last = last.prev;
                    last.next = null;
                    //cur.prev.next=cur.next;
                } else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;

                }

            }
            cur = cur.next;


        }
    }

6: clear()

清空链表:
思路:
遍历,让每个节点的prev域和next域为空即可;
但当next域为null时,当前节点就无法走到下一个节点了,所以在置空之前,先保存cur.next,即ListNode curNext=cur.next;

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

    }