链表（补充）

作者：~小明学编程 

文章专栏：Java数据结构

格言：目之所及皆为回忆，心之所想皆为过往

目录

无头双向链表

双向链表的单位结构

双向链表的主体

头插法

尾插法

从任意位置插入

 删除第一次出现关键字为key的节点

删除所有出现关键字为key的节点

查找关键字key是否在链表中

获取链表长度

打印链表

清空链表

顺序表与链表的区别

顺序表

链表

---

无头双向链表

双向链表的单位结构

class ListNode{
    public int val;
    public ListNode prev;
    public ListNode next;
    public ListNode(int val){
        this.val = val;
    }
}

首先我们把双向链表的单位节点给构造出来，其中包括我们的数据域，val用于存放不同数据类型的数据，然后就是prev前引用后next后引用，里面分别存放当前节点的前一个节点的地址和后一个节点的地址，这里我们可以把它们看作是指针分别指向前一个节点的地址和后一个节点的地址。

再下面的就是我们的构造方法，当我们创建对象的时候就给我们的对象赋上数据。

双向链表的主体

public class MyLinkedList {
    public ListNode head;//双向链表的头节点
    public ListNode last;//双向链表的尾节点
}

这里我们定义两个引用分别指向我们的头节点和尾节点，尾节点的出现方便了我们对链表实行尾插等操作，接下来我们就可以在我们的类里面写各种方法以实现链表的各种操作。

头插法

public void addFirst(int data) {
        ListNode node = new ListNode(data);
        if (this.head==null) {
            this.head = node;
            this.last = node;
        } else {
            head.prev = node;
            node.next = head;
            this.head = node;
        }
}

头插时我们需要判断一下我们的链表是否是空链表如果是空链表的话，我们的头节点和尾节点就都是当前的node节点，如果不是空链表的话就需要我们的插入操作了。

首先我们原本head的前驱是指向null的，我们先将head的前驱改为当前的node，然后我们当前的node的后驱改为当前的node,最后将我们的的node定义为新的node，由此便完成了头插。

尾插法

//尾插法
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if (this.head==null) {
            this.last = node;
            this.head = node;
        } else {
            last.next = node;
            node.prev = last;
            this.last = node;
        }
    }

与头插法一样，尾插一样先判断我们当前的链表是否为空，不是空链表的话就进行我们的尾插操作，与头插法类似尾插时首先先动我们原先的last节点的next，将原先的null，改为我们的node的地址，接着我们的node的前驱改为原先的last，由此完成连接，连接完成之后将我们的last节点改为我们的刚插入的node 节点。

从任意位置插入

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data) {
        //不合法的位置
        if(index<0) {
            return ;
        }
        //首节点选择头插
        if (index==0) {
            addFirst(data);
            return;
        }
        ListNode node = new ListNode(data);
        ListNode cur = head;
        while (index--!=0&&cur!=null) {
            cur = cur.next;
            //超出链表的范围退出
            if (cur==null) {
                return;
            }
        }
        //当前节点为尾节点选择尾插
        if (cur==last) {
            addLast(data);
        } else {
            node.next = cur;
            node.prev = cur.prev;
            cur.prev.next = node;
            cur.prev = node;
        }
//        return;
    }

从任意位置插入首先判断我们的index下标是否合法当index<0的时候插入的位置是肯定不合法的，这时我们直接return跳出函数，当我们的index==0,也就是我们的头插法，这时我们直接调用我们先前的addFirst函数即可，当我们的index>0时，我们首先创建出我们的新节点然后复制一个头节点cur来遍历我们的链表通过一个while()循环来找出我们的插入位置，当我们的index过大超出我们链表的范围的话就直接return出去，while()结束cur的位置就是我们当前要插入的位置，这时我们再进行一个判断如果我们当前插入的位置是尾节点的话就直接调用我们的addLast，否则的话就是从中间插入。

这时候也是比较复杂的一种情况需要我们移动四条指向，我们先不动cur节点先把node的前驱和后驱给定下来。

 之后我们再改变cur的前驱的后驱节点和cur的前驱节点。

 此时我们就完成了中间节点的插入。

 删除第一次出现关键字为key的节点

   //删除第一次出现关键字为key的节点
    public void remove(int key) {
        ListNode cur = head;
        //空链表
        if (cur==null) {
            return;
        }
        //首先处理头节点就是key的情况
        if(head.val==key) {
            head = head.next;
            //处理只有一个节点的空指针异常
            if (head!=null) {
                head.prev = null;
            } else {
                last = null;
            }
            return;
        }
        //处理非头节点的情况
        while (cur!=null) {
            //找到key
            if (cur.val==key) {
                //删除的位置在尾节点
                if (cur==last) {
                    cur.prev.next = cur.next;
                    last = last.prev;
                    return;
                } else {//删除的位置在中间
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                    return;
                }
            } else {
                cur = cur.next;
            }
        }
    }

首先还是我们的处理空链表异常，接着就是我们的头节点为key的情况。

 我们将我们的head头节点直接给移到下一个位置，然后将head的前驱给置空，这里要说明一个特殊情况，就是head.next为空，这时如果我们还想将它的前驱给置空的话就会出现空指针异常，因为我们的空指针没有前驱，这时就不用将前驱置空，而是将我们的last尾节点给置空，而我们原来的head节点由于没人引用了就会被jvm给回收了。

如果删除的不是头节点的话就进入我们的while()循环，cur.val==key找到我们的key,然后判断一下此时的cur是不是尾节点，是的话

 cur.prev.next = cur.next;将我们cur前驱的后驱改为cur.next也就是null，然后更新我们的last,

last = last.prev。

cur不是尾节点的话，

 我们将cur前驱的next指向cur的next,然后将cur后驱的prev指向cur的prev完成删除，中间的cur因为没人指向它会被jvm回收。

删除所有出现关键字为key的节点

   //删除所有出现关键字为key的节点
    public void removeAllKey(int key) {
        ListNode cur = head;
        //空链表
        if (cur==null) {
            return;
        }
        //处理非头节点的情况
        while (cur!=null) {
            //找到key
            if (cur.val==key) {
                //头节点
                if (cur==head) {
                    head = head.next;
                    //处理只有一个节点的空指针异常
                    if (head!=null) {
                        head.prev = null;
                    } else {
                        last = null;
                    }
                } else {
                    //删除的位置在尾节点
                    if (cur==last) {
                        cur.prev.next = cur.next;
                        last = last.prev;
//                    return;
                    } else {//删除的位置在中间
                        cur.prev.next = cur.next;
                        cur.next.prev = cur.prev;
//                    return;
                    }
                }
 
            }
            cur = cur.next;
        }
    }

删除所有出现关键字为key的节点我们只需要将处理头节点的情况放在while()循环里面并且将return去掉就能完成。

查找关键字key是否在链表中

  //查找关键字key是否在链表中
    public boolean contains(int key) {
        ListNode cur = head;
        while (cur!=null) {
            if(cur.val==key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

下面几个方法的实现与单向链表同理就不再解释了。

获取链表长度

 //获取链表长度
    public int size(){
        ListNode cur = head;
        int count = 0;
        while (cur!=null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

打印链表

//打印链表
    public void display() {
        ListNode cur = this.head;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

清空链表

//清空链表
    public void clear() {
        //head = null;
        while (head!=null) {
            ListNode cur = head.next;
            head.prev = null;
            head.next = null;
            head = cur;
        }
        last = null;
    }

顺序表与链表的区别

顺序表

优点：顺序表无论是在物理上还是在逻辑上都是连续的因为其底层是一个数组，所以顺序表在进行查找的时候会比较方便，同时也能查找指定位置的数据。

缺点：从中间或者前面的插入时间复杂度会比较高，达到了O(N)，同时顺序表的增容也比较浪费空间，因为增容的部分有可能用不完从而造成空间的浪费。

链表

优点：插入的时候及其方便时间复杂度只有O(1),同时也没有增容空间浪费的问题。

缺点：不能支持随机访问，访问的时候会比较麻烦只能通过节点的遍历来访问。