devbox
木道寻08
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【Java数据结构】初始线性表之一：链表

作者：木道寻08 | 2024-07-22 05:12:38

赞

踩

【Java数据结构】初始线性表之一：链表

为什么要有链表

上一节我们描述了顺序表：【Java数据结构】初识线性表之一：顺序表-CSDN博客

并且进行了简单模拟实现。通过源码知道，ArrayList底层使用数组来存储元素。

由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java集合中又引入了LinkedList，即链表结构。

链表

 链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。

注意：

  • 链表的结构在逻辑上是连续的，但是在物理位置上不一定连续。
  • 节点一般都是从堆上申请出来的。
  • 从堆上申请空间是按一定策略来分配的，两次申请的空间可能会连续，也可能不连续。

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

  • 单向或者双向
  • 带头或者不带头
  • 循环或者非循环

本章节我们来描述其中两种：

  1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
  2. 无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

模拟实现无头单向非循环链表

模拟实现无头单向非循环链表主要有以下的方法：

public class SingleLinkedList {
   //头插法
   public void addFirst(int data){
  }
   //尾插法
   public void addLast(int data){
  }
   //任意位置插入,第一个数据节点为0号下标
   public void addIndex(int index,int data){
  }
   //查找是否包含关键字key是否在单链表当中
   public boolean contains(int key){
       return false;
  }
   //删除第一次出现关键字为key的节点
   public void remove(int key){
  }

  //删除所有值为key的节点
   public void removeAllKey(int key){
  }
   //得到单链表的长度
   public int size(){
       return -1;
  }
   public void clear() {
  }
   
   public void display() {}
}

链表的插入：

 

链表的删除：

 模拟链表的代码实现：

  1. public class MySingLeList {
  2.     static class ListNode{
  3.         public int val;
  4.         public ListNode next;
  5.  
  6.         public ListNode(int val) {
  7.             this.val = val;
  8.         }
  9.     }
  10.     public ListNode head;
  11.  
  12.     public void createList(){
  13.         ListNode node1 = new ListNode(12);
  14.         ListNode node2 = new ListNode(34);
  15.         ListNode node3 = new ListNode(45);
  16.         ListNode node4 = new ListNode(56);
  17.         ListNode node5 = new ListNode(67);
  18.  
  19.         node1.next = node2;
  20.         node2.next = node3;
  21.         node3.next = node4;
  22.         node4.next = node5;
  23.         this.head = node1;
  24.     }
  25.  
  26.     public void display(){
  27.         ListNode tmp = this.head;
  28.         while(!(tmp == null)){
  29.             System.out.print(tmp.val+" ");
  30.             tmp = tmp.next;
  31.         }
  32.     }
  33.  
  34.     public int size(){
  35.         ListNode tmp = this.head;
  36.         int count = 0;
  37.         while(!(tmp == null)){
  38.             count++;
  39.             tmp = tmp.next;
  40.         }
  41.         return count;
  42.     }
  43.  
  44.     public boolean contains(int findData){
  45.         ListNode tmp = this.head;
  46.         while(!(tmp == null)){
  47.             if(tmp.val == findData){
  48.                 return true;
  49.             }
  50.         }
  51.         return false;
  52.     }
  53.  
  54.     public void addFirst(int data){
  55.         ListNode node = new ListNode(data);
  56.         node.next = this.head;
  57.         this.head = node;
  58.     }
  59.  
  60.     public void addLast(int data){
  61.         ListNode node = new ListNode(data);
  62.         ListNode tmp = this.head;
  63.         if(tmp == null){
  64.             this.head = node;
  65.             return;
  66.         }
  67.         while(!(tmp.next == null)){
  68.             tmp = tmp.next;
  69.         }
  70.         tmp.next = node;
  71.     }
  72.  
  73.     public void addIndex(int pos,int data){
  74.         ListNode node = new ListNode(data);
  75.         ListNode tmp = this.head;
  76.         if(pos == 0){
  77.             node.next = tmp;
  78.             this.head = node;
  79.             return;
  80.         } else if (pos == this.size()) {
  81.             this.addLast(data);
  82.         } else if (pos > this.size()) {
  83.             System.out.println("输入的位置错误！");
  84.         }else{
  85.             for (int i = 0; i < pos -1; i++) {
  86.                 tmp = tmp.next;
  87.             }
  88.             node.next = tmp.next;
  89.             tmp.next = node;
  90.         }
  91.     }
  92.  
  93.     public void remove(int data){
  94.         int flag = 1;
  95.         ListNode tmp = this.head;
  96.         if(this.head.val == data){
  97.             this.head = this.head.next;
  98.             return;
  99.         }
  100.         while(tmp.next != null){
  101.             if(tmp.next.val== data){
  102.                 flag = 0;
  103.                 break;
  104.             }
  105.             tmp = tmp.next;
  106.         }
  107.         if(flag == 0){
  108.             tmp.next = tmp.next.next;
  109.         }else{
  110.             System.out.println("链表中没有该元素！");
  111.         }
  112.     }
  113.     public void removeAll(int data){
  114.         ListNode prv = this.head;
  115.         ListNode tmp = this.head.next;
  116.         while(tmp != null){
  117.             if(tmp.val == data){
  118.                 prv.next = tmp.next;
  119.                 tmp = tmp.next;
  120.             }else{
  121.                 prv = tmp;
  122.                 tmp = tmp.next;
  123.             }
  124.         }
  125.         if(this.head.val == data){
  126.             this.head = this.head.next;
  127.         }
  128.     }
  129.  
  130.     public void clear(){
  131.         this.head = null;
  132.     }
  133. }

模拟实现无头双向链表

无头双向链表主要有以下的方法：

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

双向链表的插入：

 

双向链表的删除：

 

 模拟代码实现：

  1. public class MyLinkedList {
  2.     static class ListNode{
  3.         private int val;
  4.         private ListNode prev;
  5.         private ListNode next;
  6.  
  7.         public ListNode(int val) {
  8.             this.val = val;
  9.         }
  10.     }
  11.     ListNode head;
  12.     ListNode last;
  13.  
  14.         //头插法
  15.         public void addFirst(int data){
  16.             ListNode node = new ListNode(data);
  17.             if(head == null){
  18.                 head = node;
  19.                 last = node;
  20.             }else{
  21.                 node.next = head;
  22.                 head.prev = node;
  23.                 head = node;
  24.             }
  25.         }
  26.         //尾插法
  27.         public void addLast(int data){
  28.             ListNode node = new ListNode(data);
  29.             if(head == null){
  30.                 head = node;
  31.                 last = node;
  32.             }else{
  33.                 last.next = node;
  34.                 node.prev = last;
  35.                 last = node;
  36.             }
  37.         }
  38.         //任意位置插入,第一个数据节点为0号下标
  39.         public void addIndex(int pos,int data){
  40.             ListNode node = new ListNode(data);
  41.             ListNode cur = head;
  42.             if(pos == 0){
  43.                 addFirst(data);
  44.             }else if(pos == this.size()){
  45.                 addLast(data);
  46.             }else if(pos < 0 || pos > this.size()){
  47.                 System.out.println("插入位置错误！");
  48.             }else{
  49.                 for (int i = 0; i < pos; i++) {
  50.                     cur = cur.next;
  51.                 }
  52.                 cur.prev.next = node;
  53.                 node.prev = cur.prev;
  54.                 node.next = cur;
  55.                 cur.prev = node;
  56.             }
  57.  
  58.         }
  59.         //查找是否包含关键字key是否在单链表当中
  60.         public boolean contains(int key){
  61.             ListNode tmp = this.head;
  62.             while(!(tmp == null)){
  63.                 if(tmp.val == key){
  64.                     return true;
  65.                 }
  66.             }
  67.             return false;
  68.         }
  69.         //删除第一次出现关键字为key的节点
  70.         public void remove(int key){
  71.             ListNode cur = head;
  72.             while(cur != null){
  73.                 if(cur.val == key){
  74.                     if(cur == head){
  75.                         head = head.next;
  76.                         if(head != null){
  77.                             head.prev =null;
  78.                         }else{
  79.                             last = null;
  80.                         }
  81.                         return;
  82.                     }else if(cur == last){
  83.                         last = last.prev;
  84.                         last.next = null;
  85.                         return;
  86.                     }else{
  87.                         cur.prev.next = cur.next;
  88.                         cur.next.prev = cur.prev;
  89.                         return;
  90.                     }
  91.                 }else{
  92.                     cur = cur.next;
  93.                 }
  94.             }
  95.             System.out.println("没有该元素！");
  96.             return;
  97.         }
  98.         //删除所有值为key的节点
  99.         public void removeAllKey(int key){
  100.             ListNode cur = head;
  101.             while(cur != null){
  102.                 if(cur.val == key){
  103.                     if(cur == head){
  104.                         head = head.next;
  105.                         if(head != null){
  106.                             head.prev =null;
  107.                         }else{
  108.                             last = null;
  109.                         }
  110.                     }else if(cur == last){
  111.                         last = last.prev;
  112.                         last.next = null;
  113.                     }else{
  114.                         cur.prev.next = cur.next;
  115.                         cur.next.prev = cur.prev;
  116.                     }
  117.                 }
  118.                 cur = cur.next;
  119.             }
  120.             System.out.println("没有该元素！");
  121.             return;
  122.         }
  123.         //得到链表的长度
  124.         public int size(){
  125.             int count = 0;
  126.             ListNode cur = head;
  127.             while(cur != null){
  128.                 count++;
  129.                 cur = cur.next;
  130.             }
  131.             return count;
  132.         }
  133.         public void display(){
  134.             ListNode tmp = this.head;
  135.             while(!(tmp == null)){
  136.                 System.out.print(tmp.val+" ");
  137.                 tmp = tmp.next;
  138.             }
  139.         }
  140.         public void clear(){
  141.             ListNode cur = head;
  142.             while(cur != null){
  143.                 ListNode curNext = cur.next;
  144.                 cur.prev = null;
  145.                 cur.next = null;
  146.                 cur = curNext;
  147.             }
  148.             head = null;
  149.             last = null;
  150.         }
  151. }

LinkedList 的使用

什么是LinkedList

LinkedList的底层是双向链表结构(链表后面介绍)，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。

在集合框架中，LinkedList也实现了List接口，具体如下：

注意 ：

  • 1. LinkedList实现了List接口
  • 2. LinkedList的底层使用了双向链表
  • 3. LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问 
  • 4. LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
  • 5. LinkedList比较适合任意位置插入的场景

LinkedList 的构造方法

  1. public class Main {
  2.     public static void main(String[] args) {
  3.         List<Integer> list1 = new LinkedList<>();//无参构造
  4.  
  5.         List<Integer> list2 = new LinkedList<>();
  6.         list2.add(1);
  7.         list2.add(2);
  8.         list2.add(3);
  9.         List<Integer> list3 = new LinkedList<>(list2);//使用其他集合容器中元素构造List
  10.         list3.add(4);
  11.         System.out.println(list3);
  12.     }
  13. }

LinkedList 常用方法介绍

插入节点

  1. public class Main {
  2.     public static void main(String[] args) {
  3.         List<Integer> list1 = new LinkedList<>();
  4.         list1.add(5);
  5.         list1.add(6);
  6.         List<Integer> list2 = new LinkedList<>();
  7.         list2.add(1);//尾插
  8.         list2.add(2);
  9.         list2.add(3);
  10.         list2.add(1,4);//在指定位置插入节点
  11.         list2.addAll(list1);//尾插其他容器中的所有节点
  12.         System.out.println(list2);
  13.     }
  14. }

删除节点：

  1. public class Main {
  2.     public static void main(String[] args) {
  3.         List<Integer> list2 = new LinkedList<>();
  4.         list2.add(1);
  5.         list2.add(2);
  6.         list2.add(3);
  7.         list2.remove(1);//删除指定位置的节点
  8.         list2.remove(new Integer(3));//删除指定元素的节点
  9.         System.out.println(list2);
  10.     }
  11. }

获取指定位置的元素：

  1. public class Main {
  2.     public static void main(String[] args) {
  3.         List<Integer> list2 = new LinkedList<>();
  4.         list2.add(1);
  5.         list2.add(2);
  6.         list2.add(3);
  7.  
  8.         System.out.println(list2.get(1));
  9.     }
  10. }

更新指定位置的元素：

  1. public class Main {
  2.     public static void main(String[] args) {
  3.         List<Integer> list2 = new LinkedList<>();
  4.         list2.add(1);
  5.         list2.add(2);
  6.         list2.add(3);
  7.         list2.set(1,4);
  8.         System.out.println(list2);
  9.     }
  10. }

判断指定元素是否在链表中：

  1. public class Main {
  2.     public static void main(String[] args) {
  3.         List<Integer> list2 = new LinkedList<>();
  4.         list2.add(1);
  5.         list2.add(2);
  6.         list2.add(3);
  7.         System.out.println(list2.contains(new Integer(2)));
  8.     }
  9. }

截取部分 list

  1. public class Main {
  2.     public static void main(String[] args) {
  3.         List<Integer> list2 = new LinkedList<>();
  4.         list2.add(1);
  5.         list2.add(2);
  6.         list2.add(3);
  7.         System.out.println(list2.subList(0,2));
  8.     }
  9. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/木道寻08/article/detail/863644
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号