数据结构初阶（链表）

一、链表的基础概念

1.链表出现原理

为什么当插入和删除时，顺序表就要移动大量元素，因为相邻两元素的存储位置也具有邻居关系。它们编号是1，2，3 ,…, ，它们在内存中的位置也是挨着的，中间没有空隙， 当然就无法快速介入，而删除后，当中就会留出空隙，自然需要弥补

所以，链表是用于解决 ArrayList 中，插入、删除时间复杂度较大，且可能会浪费空间的问题

2.什么是链表

逻辑上是连续的，物理上(内存上)是不连续的，由一个个节点组成

• 对于线性表来说，总得有个头有个尾，链表也不例外。我们把链表中的第一个节点的存储位置叫做头指针，那么整个链表的存取就必须是从头指针开始进行了，之后的每一个结点，其实就是上一个的后继指针指向的位置
• 最后一个， 当然就意味着直接后继不存在了，所以我们规定，线性链表的最后一个结点指针为"空"

3.链表的分类

• 单向 / 双向
  

• 带头的 / 不带头的
  

• 循环 / 非循环
  
  重点掌握

• 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如
  哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多

• 无头双向非循环链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表

二、无头单向非循环链表

2.1 链表的底层代码

public class MyStringList {
    private ListNode head;

    class ListNode{
        private int val;
        private ListNode next;

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

    public void creatList(){
        ListNode node1 = new ListNode(12);
        ListNode node2 = new ListNode(24);
        ListNode node3 = new ListNode(36);
        ListNode node4 = new ListNode(48);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = null;

        head = node1;
    }
    //得到单链表的长度
    public int size(){
        int count = 0;
        ListNode cur = head;
        while (cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }
}

1. 单链表的读取

• 思路
  • 声明一个结点cur指向链表第一个结点;
  • 若到链表末尾 为空，则说明这个元素不存在;
  • 否则查找成功，返回结点cur的数据

    //打印这个链表的所有元素
 public void display() {
     ListNode cur = head;
     while (cur != null){
         System.out.print(cur.val + " ");
         cur = cur.next;
     }
     System.out.println();
 }

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

2. 单链表的插入

• 思路
  • 头插
    • 头插head为空无所谓
  • 尾插
    • 尾插因为是从头移到尾，如果头为空，cur.next 会造成空指针异常
  • 随意插
    • 随意插入，因为会给下标，所以要先检查下标的合理性，然后确定是头插、尾插还是随意插 ，随意插：s.next = p.next;    p.next = s;
      返回成功

 //头插法
 public void addFirst(int data){
     ListNode node = new ListNode(data);
     node.next = head;
     head = node;
 }

 //尾插法
 //要考虑是一个节点的情况
 public void addLast(int data){
     ListNode node = new ListNode(data);
     if (head == null){
         head = node;
         return;
     }

     ListNode cur = head;

     while (cur.next != null){
         cur = cur.next;
     }

     cur.next = node;
 }

 //任意位置插入,第一个数据节点为0号下标
 public void addIndex(int index,int data){
     ListNode cur = head;
     ListNode node = new ListNode(data);
     if (!checkIndex(index)){
         throw new IndexException("下标输入错误 " + index);
     }

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

     if (index == this.size()){
         addLast(data);
     }

     //找到
     for (int i = 0; i < index - 1; i++) {
         cur = cur.next;
     }

     //交换
     node.next = cur.next;
     cur.next = node;


 }

 private boolean checkIndex(int index){
     if (index < 0 || index > this.size() ){
         return false;
     }

     return true;
 }

3. 单链表的删除

• 思路
  

删除第一次出现的

• 看是否合理(为空，就不需要删除操作了，而且应该直接返回，不然访问的话，会造成空指针异常)
• 如果头结点的元素就是，那么就直接让head跳过这个节点就可以了，因为要查的是前一个结点，头结点没有前一个结点
• 接下来是查找，查的是这个元素所在结点的前一个结点
• 没有查到这个数，返回。如果查到了就进行 p.next = q.next的经典操作，前牵后

 //删除第一次出现关键字为key的节点
 public void remove(int key){
     if (head == null){
         return;
     }

     if (head.val == key){
         head = head.next;
         return;
     }

     ListNode prev = searchPrev(key);
     if (prev == null){
         System.out.println("没有这个数据");
         return;
     }
     ListNode del = prev.next;
     prev.next = del.next;
 }

 private ListNode searchPrev(int key){
     ListNode prev = head;
     while (prev.next != null){
         if (prev.next.val == key){
             return prev;
         }else{
             prev = prev.next;
         }
     }
     return null;
 }

删除全部的
因为交换是要前面的牵后面的手，头结点前面是没有结点的，所以是要从第二个结点开始找，然后最后回头看头结点的元素是不是key

 //删除所有值为key的节点
 public void removeAllKey(int key){
     if(head == null) {
         return;
     }
     
     ListNode cur = head.next;
     ListNode prev = head;
     while (cur != null) {
         if(cur.val == key) {
             prev.next = cur.next;
             cur = cur.next;
         }else {
             prev = cur;
             cur = cur.next;
         }
     }
     
     if(head.val ==  key) {
         head = head.next;
     }
 }

单链表与顺序表的时间复杂度对比

• 如果在我们不知道第i个元素的指针位置，单链表数据结构在插入和删除操作上，与线性表的顺序存储结构是没有太大优势的。
• 但如果，我们希望从第i个位置，插入10个元素
  • 对于顺序存储结构意味着，每一次插入都需要移动n-i个元素，每次都是 O(n)
  • 而单链表，我们只需要在第一次时，找到第i个位置的指针，此时为 O(n)，接下来只是简单地通过赋值移动指针而已，时间复杂度都是 0(1）

对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显

4.单链表的整表创建
单链表和顺序存储结构就不一样，它不像顺序存储结构这么集中，它可以很散是一种动态结构。对于每个链表来说，它所占用空间的大小和位置是不需要预先分配划定的，可以根据系统的情况和实际的需求即时生成

public class MyStringList {
    private ListNode head;

    class ListNode{
        private int val;
        private ListNode next;

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

    public void creatList(){
        ListNode node1 = new ListNode(12);
        ListNode node2 = new ListNode(24);
        ListNode node3 = new ListNode(36);
        ListNode node4 = new ListNode(48);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = null;

        head = node1;
    }
}

5.单链表的整表删除
思路
先用headNext记录下来头结点的下一个结点的位置，然后把头结点所存的next置空，然后依靠headNext来到后面

public void clear() {
       //this.head = null;   第一种方法
       while (head != null) {
           ListNode headNext = head.next;   //第二种方法
           head.next = null;
           head = headNext;
       }
   }

2.2 单链表例题

一、移除链表元素

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null){
            return head;
        }

        ListNode cur = head.next;
        ListNode pre = head;

        while (cur != null){
            if (cur.val == val){
                cur = cur.next;
                pre.next = cur;
            }else{
                pre = cur;
                cur = cur.next;
            }
        }

        if (head.val == val){
            head = head.next;
        }

        return head;
    }
}

二、反转一个单链表

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null){
            return null;
        }

        if (head.next == null){
            return head;
        }

        ListNode cur = head.next;
        head.next = null;

        while (cur != null){
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }

        return head;
    }
}

三、链表的中间节点

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null){
            fast= fast.next.next;
            slow = slow.next;
        }

        return slow;
    }
}

四、链表中倒数第四个节点

public ListNode FindKthToTail(ListNode head,int k) {
    ListNode fast = head;
    ListNode slow = head;

    if (head == null || k <= 0){
        return null;
    }
    for(int i = 0; i < k - 1; i++){
        fast = fast.next;
        if (fast == null){
            return null;
        }
    }

    while (fast.next != null){
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

五、合并两个有序链表

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newHead = new ListNode();
        ListNode tmpH = newHead;

        while (list1 != null && list2 != null){
            if (list1.val < list2.val){
                tmpH.next = list1;
                tmpH = tmpH.next;
                list1 = list1.next;
            }else {
                tmpH.next = list2;
                tmpH = tmpH.next;
                list2 = list2.next;
            }
        }

        if (list1 != null){
            tmpH.next = list1;
        }else {
            tmpH.next = list2;
        }

        return newHead.next;
    }
}

六、链表分割

public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        ListNode ae = null;
        ListNode as = null;
        ListNode be = null;
        ListNode bs = null;

        while (pHead != null){
            if (pHead.val < x){
                if (ae == null){
                    ae = pHead;
                    as = pHead;
                }else{
                    as.next = pHead;
                    as = as.next;
                }
            }else{
                if (be == null){
                    be = pHead;
                    bs = pHead;
                }else {
                    bs.next = pHead;
                    bs = bs.next;
                }
            }
            pHead = pHead.next;
        }

        if (ae == null){
            return be;
        }
        as.next = be;
        if (be != null){
            bs.next = null;
        }
        return ae;
    }
}

七、链表的回文结构

public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        ListNode slow = A;
        ListNode fast = A;

        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }

        //翻转
        ListNode cur = slow.next;
        while (cur != null){
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }

        //判断
        while (A != slow){
            if (A.val != slow.val){
                return false;
            }

            if (A.next == slow){
                return true;
            }

            A = A.next;
            slow = slow.next;
        }

        return true;
    }
}

八、相交链表

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode plong = headA;
        ListNode pshort = headB;

        //1、分别求两个链表的长度
        int len1 = 0;
        int len2 = 0;
        //O(M)
        while (plong != null) {
            len1++;
            plong = plong.next;
        }
        //O(N)
        while (pshort != null) {
            len2++;
            pshort = pshort.next;
        }
        plong = headA;
        pshort = headB;
        //2、求差值步的len
        int len = len1 - len2;
        if(len < 0) {
            plong = headB;
            pshort = headA;
            len = len2 - len1;
        }
        //3、哪个链表长 走len步
        while (len != 0) {
            plong = plong.next;
            len--;
        }
        //4、一起走 直到相遇！
        while (plong != pshort) {
            plong = plong.next;
            pshort = pshort.next;
        }
        return plong;
    }

九、环形列表

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null){
            return false;
        }

        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow){
                return true;
            }
        }

        return false;
    }
}

十、环形列表||

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null){
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow){
                break;
            }
        }

        if (fast == null || fast.next == null){
            return null;
        }

        fast = head;
        while (fast != slow){
            fast = fast.next;
            slow = slow.next;
        }

        return fast;
    }
}

三、无头双向非循环链表（LinkedList）

（1）什么是LInkedList

双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱

（2）LinkedList 构造方法

方法	解释
LinkLIst()	无参构造
public LinkedList(Collection<? extends E>c)	使用其他集合容器中元素构造List

List<Integer> list1 = new LinkedList<>();
List<String> list2 = new LinkedList<>();
List<String> list3 = new LinkedList<>(list2);

（3）LinkedList 方法

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 last;
        //得到链表的长度   和双向 没有关系 ！！！
        public int size(){
            int len = 0;
            ListNode cur = head;
            while (cur != null) {
                cur = cur.next;
                len++;
            }
            return len;
        }

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

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

        public void clear(){
            ListNode cur = head;
            while (cur != null) {
                ListNode curNext = cur.next;
                cur.prev = null;
                cur.next = null;
                //cur.val = null;     如果cur.val是引用的情况
                cur = curNext;
            }
            head = null;
            last = null;
        }
}

1.双链表的插入

• 头插
  • 需要看双链表是否有元素，没有元素的那么头结点和尾结点都是node
  • 如果有元素，设置好node的后驱，和head的前驱，以及改变头结点位置

  //头插法
  public void addFirst(int data){
      ListNode node = new ListNode(data);
      if(head == null) {
          head = node;
          last = node;         //第一种写法
          return;
      }
      node.next = head;
      head.prev = node;
      head = node;
  /*if(head == null) {
      head = node;
  }else {                  //第二种写法
      node.next = head;
      head.prev = node;
      head = node;
  }*/
  }

• 尾插
  • 需要看双链表是否有元素，没有元素的那么头结点和尾结点都是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;//last = last.next;
     }
 }

• 随意插思路
  • 下标是否合理，特殊情况(头插/尾插各找各妈)
  • 运用前面图的公式，设置新位置

  //任意位置插入,第一个数据节点为0号下标
  public void addIndex(int index,int data){
      int size = size();
      if(index < 0 || index > size) {
          throw new IndexOutOfBounds("双向链表index不合法！");
      }
      if(index == 0) {
          addFirst(data);
          return;
      }
      if(index == size) {
          addLast(data);
          return;
      }
      ListNode cur = head;
      while (index != 0) {
          cur = cur.next;
          index--;
      }
      ListNode node = new ListNode(data);
      node.next = cur;
      cur.prev.next = node;
      node.prev = cur.prev;
      cur.prev = node;
  }

2.双链表的删除

 //删除第一次出现关键字为key的节点
 public void remove(int key){
     ListNode cur = head;
     while (cur != null) {
         if(cur.val == key) {
             //开始删
             if(cur == head) {
                 //删除头节点
                 head = head.next;
                 //只要1个节点的时候
                 if(head != null) {
                     head.prev = null;
                 }else {
                     last = null;
                 }
             }else {
                 cur.prev.next = cur.next;
                 if(cur.next != null) {
                     //cur.prev.next = cur.next;
                     cur.next.prev = cur.prev;
                 }else {
                     //cur.prev.next = cur.next;
                     last = last.prev;
                 }
             }
             return;
         }else {
             cur = cur.next;
         }
     }
 }




 //删除所有值为key的节点
 public void removeAllKey(int key){
     ListNode cur = head;
     while (cur != null) {
         if(cur.val == key) {
             //开始删
             if (cur == head) {
                 //删除头节点
                 head = head.next;
                 //只要1个节点的时候
                 if (head != null) {
                     head.prev = null;
                 }else {
                     last = null;
                 }
             } else {
                 cur.prev.next = cur.next;
                 if (cur.next != null) {
                     //cur.prev.next = cur.next;
                     cur.next.prev = cur.prev;
                 } else {
                     //cur.prev.next = cur.next;
                     last = last.prev;
                 }
             }
         }

         cur = cur.next;
     }
 }

（4）LinkedLIst的使用

❤️方法

方法	解释
boolean add(E e)	尾插 e
void add(int index, E element)	将 e 插入到 index 位置
boolean addAll(Collection<? extends E> c)	尾插 c 中的元素
E remove(int index)	删除 index 位置元素
boolean remove(Object o)	删除遇到的第一个 o
E get(int index)	获取下标 index 位置元素
E set(int index, E element)	将下标 index 位置元素设置为 element
void clear()	清空
boolean contains(Object o)	判断 o 是否在线性表中
int indexOf(Object o)	返回第一个 o 所在下标
int lastIndexOf(Object o)	返回最后一个 o 的下标
List subList(int fromIndex, int toIndex)	截取部分 list

❤️遍历

public static void main(String[] args) {
	LinkedList<Integer> list = new LinkedList<>();
	list.add(1); // add(elem): 表示尾插
	list.add(2);
	list.add(3);
	list.add(4);
	list.add(5);
	list.add(6);
	list.add(7);
	System.out.println(list.size());

	//直接打印
	System.out.println(linkedList);
	
	// foreach遍历
	for (int e:list) {
		System.out.print(e + " ");
	}
	System.out.println();
	
	// 使用迭代器遍历---正向遍历
	ListIterator<Integer> it = list.listIterator();
	while(it.hasNext()){
		System.out.print(it.next()+ " ");
	}
	System.out.println();
	
	// 使用反向迭代器---反向遍历
	ListIterator<Integer> rit = list.listIterator(list.size());
	while (rit.hasPrevious()){
		System.out.print(rit.previous() +" ");
	}
	System.out.println();
}

四 顺序存储和链式存储的区别

不同点	顺序存储	链式存储
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持：O(N)
头插	需要搬移元素，效率低O(N)	只需修改引用的指向，时间复杂度为O(1)
插入	空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁