LinkedList简介

Java LinkedList（链表）类似于 ArrayList，是一种常用的数据容器。 与 ArrayList 相比，LinkedList 的增加和删除的操作效率更高，而查找和修改的操作效率较低。

LinkedList底层是一个双向链表，如下：

一个双向链表有三个整数值: 数值、向后的节点链接、向前的节点链接

双向链表有头节点和尾结点。

因此要实现双向链表，我们就要用类将双向链表的各个部分给抽取出来

  static class ListNode{

       public int val;//数据域

       public ListNode prev;//保存前一个节点的地址

       public ListNode next;//保存后一个结点的地址

       public ListNode(int val) {

           this.val = val;

       }

   }

   public ListNode head;//头节点

   public ListNode tail;//尾结点

头插法创建链表

要用头插法建立双向链表，与单链表不同，双向链表的每一个结点都有三个域，因此我们要想清楚改哪个地方，看下图：

由图我我们可知，我们要改变插入结点的next域，要改变头节点的prev域，然后将插入结点的prev置为null，最后让头节点指向插入的结点，这样在头结点插入一个结点就完成了。

但这个只是一般情况下插入，还有一种特殊情况，就是遇到空链表。

如果是空链表的情况，那么头节点就是要插入的这个结点，尾节点也是要插入的这个结点。

  public void addFirst(int data){

       ListNode node = new ListNode(data);

       //空链表

       if(this.head == null){

           this.head = node;

           this.tail = node;

       }else {

           node.next = this.head;

           this.head.prev = node;

           this.head = node;

       }

   }

尾插法创建链表

看上图，我们可知用尾插法插入一个结点，要改变尾结点的next域，将要插入的next域置为空，将插入结点的prev域指向尾结点，再将尾节点指向要插入的结点就可以了。

同时也不要忘记考虑空链表的情况，与头插法相同，如果为空，那么要插入的这个结点就既是头结点也是尾结点。

  public void addLast(int data){

       ListNode node = new ListNode(data);

       //空链表

       if(this.head == null){

           this.head = node;

           this.tail = node;

       }else {

           this.tail.next = node;

           node.prev = this.tail;

           this.tail = node;

       }

   }

任意位置插入,第一个数据节点为0号下标

在插入数据时，我们首先要对要插入的位置index进行判断，判断index是否合法，index 位置合法才能插入数据。其次我们要考虑index在特殊位置，例如：在头节点和尾结点进行插入数据。

  /**

    * 任意位置插入,第一个数据节点为0号下标

    * @param index

    * 要对index位置判断是否合法

    * index在特殊位置 -头插和尾插

    * @param data

    * @return

    */

   public boolean addIndex(int index,int data){

       if(index<0 || size()<index){

           System.out.println("index位置不合法");

           return false;

       }

       if(index == 0){

           addFirst(data);

           return true;

       }

       if(index == size()){

           addLast(data);

           return true;

       }

       ListNode node = new ListNode(data);

       ListNode cur = findIndexListNode(index);

       node.next = cur;

       cur.prev.next = node;

       node.prev = cur.prev;

       cur.prev = node;

       return false;

   }

   public ListNode findIndexListNode(int index){

       ListNode cur = this.head;

       while(index != 0){

           cur = cur.next;

           index--;

       }

       return cur;

   }

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

查找是否包含关键字key，也就是遍历链表，与各个节点的数据域进行比较，如果相等就返回true，如果不相等，就返回false。

   //查找是否包含关键字key是否在单链表当中

   public boolean contains(int key){

       ListNode cur = this.head;

       while(cur != null){

           if(cur.val == key){

               return true;

           }

           cur= cur.next;

       }

       return false;

   }

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

删除双向链表的节点,首先要明确我们要改那些值,看下图:

假设删除的是值为3的结点,那么此时要改变两个地方的值,就是删除结点前一个结点的next,以及后一个结点的prev.改完之后,就可以让值为2的结点直接找到值为4的结点,值为4的节点也可以直接找到值为2的结点.

然后我们还要考虑到删除的结点在特殊的位置,有两种情况:1.删除的结点在头节点或者是尾结点 2.只有一个结点

   /**

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

    * 可能会遇到的特殊情况

    *    1.删除的节点在头或者尾

    *    2.只有一个结点

    * @param key

    */

   public void remove(int key){

       ListNode cur = this.head;

       while(cur != null){

           if(cur.val == key){

               if(cur==head){//头节点

                   if(cur.next==null){//只有一个结点

                       this.head = null;

                       this.tail = null;

                       return;

                   }

                   this.head = head.next;

                   this.head.prev = null;

               }else{

                   cur.prev.next = cur.next;

                   if(cur.next != null){

                       cur.next.prev = cur.prev;

                   }else{//删除的是尾结点的情况

                       this.tail = cur.prev;

                   }

               }

               return;

           }else{

               cur = cur.next;

           }

       }

   }

删除所有值为key的节点

删除所有为key的结点,只需要在前面删除一个为key的结点代码上,把return删了就可以了.

  //删除所有值为key的节点

   public void removeAllKey(int key){

       ListNode cur = this.head;

       while(cur != null){

           if(cur.val == key){

               if(cur==head){

                   if(cur.next==null){

                       this.head = null;

                       this.tail = null;

                       return;

                   }

                   this.head = head.next;

                   this.head.prev = null;

               }else{

                   cur.prev.next = cur.next;

                   if(cur.next != null){

                       cur.next.prev = cur.prev;

                   }else{

                       this.tail = cur.prev;

                   }

               }

           }

           cur = cur.next;

       }

   }

得到链表的长度

得到链表的长度，实际上就相当于遍历了一边链表，如果当前节点不为空count就+1，最后return count就可以了。

  //得到单链表的长度

   public int size(){

       ListNode cur = head;

       int count = 0;

       while(cur != null){

           count++;

           cur = cur.next;

       }

       return count;

   }

打印链表

打印双向链表，我们可以从前往后进行打印，也可以从后往前打印。一般打印链表都是从前往后打印。具体代码实现如下：

  public void display(){

       ListNode cur = head;

       while(cur != null){

           System.out.print(cur.val+" ");

           cur = cur.next;

       }

   }

清空链表

清空双向链表，不能直接将头节点和尾节点置为null

因为这是双向链表，直接置为null也可能会有别的结点引用,所以双向链表只能一个一个置空

   public void clear(){

       //error

       /*this.head = null;

       this.tail = null;*/

       ListNode cur= this.head;

       while(cur != null){

           ListNode curNext = cur.next;

           cur.prev = null;

           cur.next = null;

           cur = curNext;

       }

       this.head = null;

       this.tail = null;

   }

完整代码：

import java.util.List;

public class MyLinkedList {

   static class ListNode{

       public int val;

       public ListNode prev;

       public ListNode next;

       public ListNode(int val) {

           this.val = val;

       }

   }

   public ListNode head;

   public ListNode tail;

   /**

    * 无头双向链表实现

    * @param data

    */

   //头插法

   public void addFirst(int data){

       ListNode node = new ListNode(data);

       //空链表

       if(this.head == null){

           this.head = node;

           this.tail = node;

       }else {

           node.next = this.head;

           this.head.prev = node;

           this.head = node;

       }

   }

   //尾插法

   public void addLast(int data){

       ListNode node = new ListNode(data);

       //空链表

       if(this.head == null){

           this.head = node;

           this.tail = node;

       }else {

           this.tail.next = node;

           node.prev = this.tail;

           this.tail = node;

       }

   }

   /**

    * 任意位置插入,第一个数据节点为0号下标

    * @param index

    * 要对index位置判断是否合法

    * index在特殊位置 -头插和尾插

    * @param data

    * @return

    */

   public boolean addIndex(int index,int data){

       if(index<0 || size()<index){

           System.out.println("index位置不合法");

           return false;

       }

       if(index == 0){

           addFirst(data);

           return true;

       }

       if(index == size()){

           addLast(data);

           return true;

       }

       ListNode node = new ListNode(data);

       ListNode cur = findIndexListNode(index);

       node.next = cur;

       cur.prev.next = node;

       node.prev = cur.prev;

       cur.prev = node;

       return false;

   }

   public ListNode findIndexListNode(int index){

       ListNode cur = this.head;

       while(index != 0){

           cur = cur.next;

           index--;

       }

       return cur;

   }

   //查找是否包含关键字key是否在单链表当中

   public boolean contains(int key){

       ListNode cur = this.head;

       while(cur != null){

           if(cur.val == key){

               return true;

           }

           cur= cur.next;

       }

       return false;

   }

   /**

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

    * 可能会遇到的特殊情况

    *    1.删除的节点在头或者尾

    *    2.只有一个结点

    * @param key

    */

   public void remove(int key){

       ListNode cur = this.head;

       while(cur != null){

           if(cur.val == key){

               if(cur==head){

                   if(cur.next==null){

                       this.head = null;

                       this.tail = null;

                       return;

                   }

                   this.head = head.next;

                   this.head.prev = null;

               }else{

                   cur.prev.next = cur.next;

                   if(cur.next != null){

                       cur.next.prev = cur.prev;

                   }else{

                       this.tail = cur.prev;

                   }

               }

               return;

           }else{

               cur = cur.next;

           }

       }

   }

   //删除所有值为key的节点

   public void removeAllKey(int key){

       ListNode cur = this.head;

       while(cur != null){

           if(cur.val == key){

               if(cur==head){

                   if(cur.next==null){

                       this.head = null;

                       this.tail = null;

                       return;

                   }

                   this.head = head.next;

                   this.head.prev = null;

               }else{

                   cur.prev.next = cur.next;

                   if(cur.next != null){

                       cur.next.prev = cur.prev;

                   }else{

                       this.tail = cur.prev;

                   }

               }

           }

           cur = cur.next;

       }

   }

   //得到单链表的长度

   public int size(){

       ListNode cur = head;

       int count = 0;

       while(cur != null){

           count++;

           cur = cur.next;

       }

       return count;

   }

   public void display(){

       ListNode cur = head;

       while(cur != null){

           System.out.print(cur.val+" ");

           cur = cur.next;

       }

   }

   public void clear(){

       //error

       this.head = null;

       this.tail = null;

      /* ListNode cur= this.head;

       while(cur != null){

           ListNode curNext = cur.next;

           cur.prev = null;

           cur.next = null;

           cur = curNext;

       }

       this.head = null;

       this.tail = null;*/

   }

}

总结:

LinkedList作为Java中的一个重要集合,底层是个双向链表,我只是模拟实现了一些简单的功能,大家如果要研究LinkedList底层到底是怎么实现的,大家开始去看源码比较好.