概述

链表在计算机中内存的分配是不连续的，但是每个节点都有一个指向下一个节点的next引用，（双向链表还有一个指向前一个节点的prev引用），只要获得链表的头，那么剩下的元素都很容易获取了。所以链表的每个节点有2个组成部分，一个是存放数据的数据域，一个是指向前驱或后继的引用。

链表分类

单链表（带头）

public class SingleLinkedListIncludeHead
   
    {
       private Node
    
      head;    class Node
     
      {
           protected E element;        protected Node
      
        next;        public Node(E data){
               this.element = data;        }    }    @SuppressWarnings("unchecked")    public SingleLinkedListIncludeHead(){
           head = new Node<>((E)new Object());    }    //头插法 head之后去添加元素    public void addHead(E data){
           //创建新节点        Node
       
         newNode = new Node<>(data);        //绑定新节点的next        newNode.next = head.next;        //head.next指向新节点        head.next = newNode;    }    //尾插法    public void addTail(E data){
           //创建新节点        Node
        
          newNode = new Node<>(data); //遍历当前链表，找到最后一个节点 Node
         
           tmp = head; while(tmp.next != null){ tmp = tmp.next; } //绑定最后的一个节点的next tmp.next = newNode; } public boolean delete(E data){ //head节点需要单独处理 if(head.element == data){ head = head.next; return true; } //删除某一个正常节点 Node
          
            tmp = head; while(tmp.next != null){ if(tmp.next.element == data){ tmp.next = tmp.next.next; return true; } tmp = tmp.next; } return false; } //返回指定位置的节点 public Node
           
             findValue(int index){ if(index < 0) return null; Node
            
              tmp = head; while(tmp.next != null && index-- > 0){ tmp = tmp.next; } if(index <= 0) { return tmp; } return null; } //得到当前链表的长度 public int getLength(){ int size = 0; Node
             
               tmp = head; while(tmp.next != null){ size++; tmp = tmp.next; } return size; } //遍历链表 public String toString(){ StringBuilder sb = new StringBuilder(); Node
              
                tmp = head; while(tmp.next != null){ sb.append(tmp.next.element).append(" "); tmp = tmp.next; } return sb.toString(); }}

单链表（不带头）

不带头节点的单链表基本同上，不同的地方即带头单链表在new的时候就有一个空节点，但是不带头的单链表在第一次add节点的时候才有第一个节点。

循环链表

循环链表的特点是最后一个节点的next引用指向头节点，构成循环。

所以在尾插插入节点的时候，要把插入的节点的next指向头节点，并把插入的节点的上一个节点的next指向插入的节点。

删除节点的时候，要把删除的节点的上一个节点的next指向删除节点的下一个节点，如果删除的节点是最后一个，那么需要把删除节点的上一个节点的next指向头节点即可。

双向链表

双向链表的特点是内部Node类的引用域多了一个prev，即指向前一个节点的引用。

所以在尾插插入节点的时候，要把插入的节点的next指向null，prev指向原来链表的最后一个节点。

删除节点的时候，要把删除节点的上一个节点的next指向删除节点的下一个节点，把删除节点的下一个节点的prev指向删除节点的上一个节点，如果删除的节点是最后一个，那么需要把删除节点的上一个节点的next指向null即可。

双向循环链表

双向循环列表的特点是最后一个节点的next引用指向头节点，同时头节点的prev引用指向最后一个节点，构成循环。

所以在尾插插入节点的时候，要把插入的节点的next指向头节点，并把插入的节点的上一个节点的next指向插入的节点的同时，还要把插入的节点的prev指向它的上一个节点，并把头节点的prev指向插入的节点。

删除节点的时候，要把删除节点的上一个节点的next指向删除节点的下一个节点，并把删除节点的下一个节点的prev指向删除节点的上一个节点。

总结

链表的节点依靠next和prev引用一个连着一个，这样如果在链表中设置两个指向头节点和尾节点的引用，就可以让插入或删除节点的时间复杂度降低到常数，但是读取的时间复杂度依然是线性的，因为链表没法像数组一样快速定位到某一个节点（或数据）。

链表相关练习题

1.逆序打印单链表

因为要逆序打印，所以要先遍历单链表至最后一个节点，然后一级一级往前，可以考虑递归。

public void reversePrintList(Node head){
           if(head == null){
               return;        }        reversePrintList(head.next);        System.out.println(head.element + " ");    }

2.判断链表是否成环

快慢指针法，定义两个引用都从头节点开始向后移动，快指针一次移动两个节点，慢指针一次移动一个节点，如果他们在某一个时刻移动到了同一个节点上（相遇），就说明链表是有环的，否则没有环。（如果链表没有环，他们永远不会相遇。）

public boolean isLoopLinkedList(MyLinkedList x) {
           if (x.head == null || x.head.next == null) return false;        MyLinkedList.Node slow = x.head;        MyLinkedList.Node fast = x.head;        while (fast.next != null && fast.next.next != null) {
   //判空，避免空指针异常。            slow = slow.next;            fast = fast.next.next;            if (slow == fast) {
                   return true;            }        }        return false;    }

3.如何确定链表在何处入环

在2题的基础上，快慢两个指针一定在环的某个节点相遇，相遇时的图如下：

假设C点为相遇点，B点为入环点，A点为链表的头节点，那么快指针走的路程为m+n+x+n=m+2n+x，慢指针走的路程为m+n

又因为快指针的速度是慢指针的二倍，所以快指针的路程也应该为慢指针的二倍，所以m+2n+x = 2(m+n)，解得x = m，即从第一次相遇点到入环点的距离，等于从头节点到入环点的距离。

那么，他们第一次在C点相遇后，我让快慢指针的步长都为1，并且把快指针拉回链表头节点，让它们一个从C点开始走，步长为1，一个从A点开始走，步长为1，那么他们再次相遇的节点就是入环点。

转载地址：http://lfwqi.baihongyu.com/

你可能感兴趣的文章