• 数据结构——单项链表

    目录

    一. 认识链表

    二、链表和数组

    数组: 

     链表 

    三、链表封装

    1、创建链表类

    2、链表常见操作

    四、 链表操作

    1、尾部追加数据 - append方法实现

    2、任意位置插入

    3、位置移除数据

    4、获取元素位置

    5、移除指定元素

    6、toString

    五、完整代码

    一. 认识链表

    链表和数组一样, 可以用于存储一系列的元素, 但是链表和数组的实现机制完全不同.

    链表的数据结构：

     

    二、链表和数组

    数组: 

    - 要存储多个元素，数组（或列表）可能是最常用的数据结构。
    - 我们之前说过, 几乎每一种编程语言都有默认实现数组结构, 这种数据结构非常方便，提供了一个便利的`[]`语法来访问它的元素。
    - 但是数组也有很多缺点: 
      - 数组的创建通常需要申请一段连续的内存空间(一整块的内存), 并且大小是固定的(大多数编程语言数组都是固定的), 所以当当前数组不能满足容量需求时, 需要扩容. (一般情况下是申请一个更大的数组, 比如2倍. 然后将原数组中的元素复制过去)
      - 而且在数组开头或中间位置插入数据的成本很高, 需要进行大量元素的位移.（尽管我们已经学过的JavaScript的`Array`类方法可以帮我们做这些事，但背后的原理依然是这样）。

     链表 

    - 要存储多个元素, 另外一个选择就是使用链表.
    - 但不同于数组, 链表中的元素在内存中不必是连续的空间.
    - 链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(有些语言称为指针或者链接)组成.
    - 相对于数组, 链表有一些优点: 
      - 内存空间不是比是连续的. 可以充分利用计算机的内存. 实现灵活的内存动态管理.
      - 链表不必在创建时就确定大小, 并且大小可以无限的延伸下去.
      - 链表在插入和删除数据时, 时间复杂度可以达到O(1). 相对数组效率高很多.
    - 相对于数组, 链表有一些缺点: 
      - 链表访问任何一个位置的元素时, 都需要从头开始访问.(无法跳过第一个元素访问任何一个元素).
      - 无法通过下标直接访问元素, 需要从头一个个访问, 直到找到对应的位置.

    三、链表封装

    1、创建链表类

    1. // 封装链表的构造函数
    2. function LinkedList() {
    3.     // 封装一个Node类, 用于保存每个节点信息
    4.     function Node(element) {
    5.         this.element = element
    6.         this.next = null
    7.     }
    8.  
    9.     // 链表中的属性
    10.     this.length = 0  // 链表的长度
    11.     this.head = null // 链表的第一个节点
    12.     
    13.     // 链表中的方法
    14. }

    • 封装LinkedList的类, 用于表示我们的链表结构. (和Java中的链表同名, 不同Java中的这个类是一个双向链表, 后面我们会讲解双向链表)

    • 在LinkedList类中有一个Node类, 用于封装每一个节点上的信息.(和优先级队列的封装一样)

    • 链表中我们保存两个属性, 一个是链表的长度, 一个是链表中第一个节点.

    • 当然, 还有很多链表的操作方法. 我们放在下一节中学习.

    2、链表常见操作

    -  `append(element)`：向列表尾部添加一个新的项
    -  `insert(position, element)`：向列表的特定位置插入一个新的项。
    -  `remove(element)`：从列表中移除一项。
    -  `indexOf(element)`：返回元素在列表中的索引。如果列表中没有该元素则返回`-1`。
    -  `removeAt(position)`：从列表的特定位置移除一项。
    -  `isEmpty()`：如果链表中不包含任何元素，返回`true`，如果链表长度大于0则返回`false`。
    -  `size()`：返回链表包含的元素个数。与数组的`length`属性类似。
    -  `toString()`：由于列表项使用了`Node`类，就需要重写继承自JavaScript对象默认的`toString`方法，让其只输出元素的值。

    四、 链表操作

    1、尾部追加数据 - append方法实现

    - 向链表尾部追加数据可能有两种情况:

      - 链表本身为空, 新添加的数据时唯一的节点.
      - 链表不为空, 需要向其他节点后面追加节点.

    1.        // 节点的结构
    2.         class Lnode {
    3.             constructor(data) {
    4.                 this.data = data;
    5.                 this.next = null;
    6.             }
    7.         }
    8.         // 链表的结构
    9.         class LinkList {
    10.             constructor() {
    11.                 this.head = null;
    12.                 this.length = 0;
    13.             }
    14.             append(ele) {
    15.                 // 创建新节点
    16.                 let newnode = new Lnode(ele);
    17.                 console.log(newnode);
    18.                 if (this.head == null) {
    19.                     this.head = newnode;
    20.                 } else {
    21.                     let current = this.head;
    22.                     while (current.next != null) {
    23.                         // 继续找
    24.                         current = current.next
    25.                     };
    26.                     current.next = newnode;
    27.                 }
    28.                 this.length++
    29.             }
    30.         }
    31.         let list = new LinkList();
    32.         for (let i = 0; i < 5; i++) {
    33.             list.append(i)
    34.         }
    35.         console.log(list);

    2、任意位置插入

    1.    // 节点的结构
    2.         class Lnode {
    3.             constructor(data) {
    4.                 this.data = data;
    5.                 this.next = null;
    6.             }
    7.         }
    8.         // 链表的结构
    9.         class LinkList {
    10.             constructor() {
    11.                 this.head = null;
    12.                 this.length = 0;
    13.             }
    14.             append(ele) {
    15.                 // 创建新节点
    16.                 let newnode = new Lnode(ele);
    17.                 // console.log(newnode);
    18.                 if (this.head == null) {
    19.                     this.head = newnode;
    20.                 } else {
    21.                     let current = this.head;
    22.                     while (current.next != null) {
    23.                         // 继续找
    24.                         current = current.next
    25.                     };
    26.                     current.next = newnode;
    27.                 }
    28.                 this.length++
    29.             }
    30.            
    31.             insert(position,ele) {
    32.                 if(position<0||position>this.length||!Number.isInteger(position)){
    33.                     return false
    34.                 }
    35.                 let newnode=new Lnode(ele)
    36.                 // 头部位置插入
    37.                 if(position==0) {
    38.                     if(this.head==null) {
    39.                         this.head==newnode
    40.                     }else {
    41.                         newnode.next=this.head
    42.                         this.head=newnode
    43.                     }
    44.                     this.length++
    45.                 }else if(position==this.length) {  //最后位置
    46.                     this.append(ele)
    47.                 }else {//任意位置
    48.                     let current =this.head
    49.                     let index=0
    50.                     while(index1) {
    51.                         current=current.next
    52.                         index++
    53.                     }
    54.                     newnode.next=current.next
    55.                     current.next=newnode
    56.                     this.length++
    57.                 }
    58.             }
    59.         }
    60.         let list = new LinkList();
    61.         for (let i = 0; i < 5; i++) {
    62.             list.append(i)
    63.         }
    64.         list.insert(1,8)
    65.         console.log(list);

    3、位置移除数据

    1.         // 节点的结构
    2.         class Lnode {
    3.             constructor(data) {
    4.                 this.data = data;
    5.                 this.next = null;
    6.             }
    7.         }
    8.         // 链表的结构
    9.         class LinkList {
    10.             constructor() {
    11.                 this.head = null;
    12.                 this.length = 0;
    13.             }
    14.             append(ele) {
    15.                 // 创建新节点
    16.                 let newnode = new Lnode(ele);
    17.                 // console.log(newnode);
    18.                 if (this.head == null) {
    19.                     this.head = newnode;
    20.                 } else {
    21.                     let current = this.head;
    22.                     while (current.next != null) {
    23.                         // 继续找
    24.                         current = current.next
    25.                     };
    26.                     current.next = newnode;
    27.                 }
    28.                 this.length++
    29.             }
    30.  
    31.             insert(position, ele) {
    32.                 if (position < 0 || position > this.length || !Number.isInteger(position)) {
    33.                     return false
    34.                 }
    35.                 let newnode = new Lnode(ele)
    36.                 // 头部位置插入
    37.                 if (position == 0) {
    38.                     if (this.head == null) {
    39.                         this.head == newnode
    40.                     } else {
    41.                         newnode.next = this.head
    42.                         this.head = newnode
    43.                     }
    44.                     this.length++
    45.                 } else if (position == this.length) {  //最后位置
    46.                     this.append(ele)
    47.                 } else {//任意位置
    48.                     let current = this.head
    49.                     let index = 0
    50.                     while (index < position - 1) {
    51.                         current = current.next
    52.                         index++
    53.                     }
    54.                     newnode.next = current.next
    55.                     current.next = newnode
    56.                     this.length++
    57.                 }
    58.             }
    59.  
    60.             removeAt(position) {
    61.                 //检验格式
    62.                 if (position < 0 || position > this.length - 1 || !Number.isInteger(position)) {
    63.                     return false
    64.                 }//为空就不用移除了
    65.                 if (this.head == null) {
    66.                     return
    67.                 } else {
    68.                     //移除头部
    69.                     if (position == 0) {
    70.                         this.head = this.head.next
    71.                     } else {//移除尾部或者中间
    72.                         let current = this.head,
    73.                         index = 0
    74.                         while (index < position - 1) {
    75.                             current = current.next
    76.                             index++
    77.                         }
    78.                         current.next = current.next.next
    79.                     }
    80.                     this.length--
    81.                 }
    82.             }
    83.  
    84.         }
    85.         let list = new LinkList();
    86.         for (let i = 0; i < 5; i++) {
    87.             list.append(i)
    88.         }
    89.         list.removeAt(4)
    90.         console.log(list);

    4、获取元素位置

    1.     // 节点的结构
    2.         class Lnode {
    3.             constructor(data) {
    4.                 this.data = data;
    5.                 this.next = null;
    6.             }
    7.         }
    8.         // 链表的结构
    9.         class LinkList {
    10.             constructor() {
    11.                 this.head = null;
    12.                 this.length = 0;
    13.             }
    14.             append(ele) {
    15.                 // 创建新节点
    16.                 let newnode = new Lnode(ele);
    17.                 // console.log(newnode);
    18.                 if (this.head == null) {
    19.                     this.head = newnode;
    20.                 } else {
    21.                     let current = this.head;
    22.                     while (current.next != null) {
    23.                         // 继续找
    24.                         current = current.next
    25.                     };
    26.                     current.next = newnode;
    27.                 }
    28.                 this.length++
    29.             }
    30.  
    31.             insert(position, ele) {
    32.                 if (position < 0 || position > this.length || !Number.isInteger(position)) {
    33.                     return false
    34.                 }
    35.                 let newnode = new Lnode(ele)
    36.                 // 头部位置插入
    37.                 if (position == 0) {
    38.                     if (this.head == null) {
    39.                         this.head == newnode
    40.                     } else {
    41.                         newnode.next = this.head
    42.                         this.head = newnode
    43.                     }
    44.                     this.length++
    45.                 } else if (position == this.length) {  //最后位置
    46.                     this.append(ele)
    47.                 } else {//任意位置
    48.                     let current = this.head
    49.                     let index = 0
    50.                     while (index < position - 1) {
    51.                         current = current.next
    52.                         index++
    53.                     }
    54.                     newnode.next = current.next
    55.                     current.next = newnode
    56.                     this.length++
    57.                 }
    58.             }
    59.  
    60.             removeAt(position) {
    61.                 //检验格式
    62.                 if (position < 0 || position > this.length - 1 || !Number.isInteger(position)) {
    63.                     return false
    64.                 }//为空就不用移除了
    65.                 if (this.head == null) {
    66.                     return
    67.                 } else {
    68.                     //移除头部
    69.                     if (position == 0) {
    70.                         this.head = this.head.next
    71.                     } else {//移除尾部或者中间
    72.                         let current = this.head,
    73.                         index = 0
    74.                         while (index < position - 1) {
    75.                             current = current.next
    76.                             index++
    77.                         }
    78.                         current.next = current.next.next
    79.                     }
    80.                     this.length--
    81.                 }
    82.             }
    83.  
    84.             indexOf(ele) {
    85.                 let current=this.head,index=0
    86.                 while(index<this.length) {
    87.                     if(current.data==ele) {
    88.                         return index
    89.                     }else {
    90.                         current=current.next
    91.                         index++
    92.                     }
    93.                 }
    94.                 return -1
    95.             }
    96.  
    97.         }
    98.         let list = new LinkList();
    99.         for (let i = 0; i < 5; i++) {
    100.             list.append(i)
    101.         }
    102.         console.log(list.indexOf(2));  //2

    5、移除指定元素

    1.     // 节点的结构
    2.         class Lnode {
    3.             constructor(data) {
    4.                 this.data = data;
    5.                 this.next = null;
    6.             }
    7.         }
    8.         // 链表的结构
    9.         class LinkList {
    10.             constructor() {
    11.                 this.head = null;
    12.                 this.length = 0;
    13.             }
    14.             append(ele) {
    15.                 // 创建新节点
    16.                 let newnode = new Lnode(ele);
    17.                 // console.log(newnode);
    18.                 if (this.head == null) {
    19.                     this.head = newnode;
    20.                 } else {
    21.                     let current = this.head;
    22.                     while (current.next != null) {
    23.                         // 继续找
    24.                         current = current.next
    25.                     };
    26.                     current.next = newnode;
    27.                 }
    28.                 this.length++
    29.             }
    30.  
    31.             insert(position, ele) {
    32.                 if (position < 0 || position > this.length || !Number.isInteger(position)) {
    33.                     return false
    34.                 }
    35.                 let newnode = new Lnode(ele)
    36.                 // 头部位置插入
    37.                 if (position == 0) {
    38.                     if (this.head == null) {
    39.                         this.head == newnode
    40.                     } else {
    41.                         newnode.next = this.head
    42.                         this.head = newnode
    43.                     }
    44.                     this.length++
    45.                 } else if (position == this.length) {  //最后位置
    46.                     this.append(ele)
    47.                 } else {//任意位置
    48.                     let current = this.head
    49.                     let index = 0
    50.                     while (index < position - 1) {
    51.                         current = current.next
    52.                         index++
    53.                     }
    54.                     newnode.next = current.next
    55.                     current.next = newnode
    56.                     this.length++
    57.                 }
    58.             }
    59.  
    60.             removeAt(position) {
    61.                 //检验格式
    62.                 if (position < 0 || position > this.length - 1 || !Number.isInteger(position)) {
    63.                     return false
    64.                 }//为空就不用移除了
    65.                 if (this.head == null) {
    66.                     return
    67.                 } else {
    68.                     //移除头部
    69.                     if (position == 0) {
    70.                         this.head = this.head.next
    71.                     } else {//移除尾部或者中间
    72.                         let current = this.head,
    73.                         index = 0
    74.                         while (index < position - 1) {
    75.                             current = current.next
    76.                             index++
    77.                         }
    78.                         current.next = current.next.next
    79.                     }
    80.                     this.length--
    81.                 }
    82.             }
    83.  
    84.             indexOf(ele) {
    85.                 let current=this.head,index=0
    86.                 while(index<this.length) {
    87.                     if(current.data==ele) {
    88.                         return index
    89.                     }else {
    90.                         current=current.next
    91.                         index++
    92.                     }
    93.                 }
    94.                 return -1
    95.             }
    96.  
    97.  
    98.             remove(ele) {
    99.                 let index=this.indexOf(ele)
    100.                 this.removeAt(index)
    101.             }
    102.  
    103.         }
    104.         let list = new LinkList();
    105.         for (let i = 0; i < 5; i++) {
    106.             list.append(i)
    107.         }
    108.         console.log(list.indexOf(2));

    6、toString

    1.   // 节点的结构
    2.         class Lnode {
    3.             constructor(data) {
    4.                 this.data = data;
    5.                 this.next = null;
    6.             }
    7.         }
    8.         // 链表的结构
    9.         class LinkList {
    10.             constructor() {
    11.                 this.head = null;
    12.                 this.length = 0;
    13.             }
    14.             append(ele) {
    15.                 // 创建新节点
    16.                 let newnode = new Lnode(ele);
    17.                 // console.log(newnode);
    18.                 if (this.head == null) {
    19.                     this.head = newnode;
    20.                 } else {
    21.                     let current = this.head;
    22.                     while (current.next != null) {
    23.                         // 继续找
    24.                         current = current.next
    25.                     };
    26.                     current.next = newnode;
    27.                 }
    28.                 this.length++
    29.             }
    30.  
    31.             insert(position, ele) {
    32.                 if (position < 0 || position > this.length || !Number.isInteger(position)) {
    33.                     return false
    34.                 }
    35.                 let newnode = new Lnode(ele)
    36.                 // 头部位置插入
    37.                 if (position == 0) {
    38.                     if (this.head == null) {
    39.                         this.head == newnode
    40.                     } else {
    41.                         newnode.next = this.head
    42.                         this.head = newnode
    43.                     }
    44.                     this.length++
    45.                 } else if (position == this.length) {  //最后位置
    46.                     this.append(ele)
    47.                 } else {//任意位置
    48.                     let current = this.head
    49.                     let index = 0
    50.                     while (index < position - 1) {
    51.                         current = current.next
    52.                         index++
    53.                     }
    54.                     newnode.next = current.next
    55.                     current.next = newnode
    56.                     this.length++
    57.                 }
    58.             }
    59.  
    60.             removeAt(position) {
    61.                 //检验格式
    62.                 if (position < 0 || position > this.length - 1 || !Number.isInteger(position)) {
    63.                     return false
    64.                 }//为空就不用移除了
    65.                 if (this.head == null) {
    66.                     return
    67.                 } else {
    68.                     //移除头部
    69.                     if (position == 0) {
    70.                         this.head = this.head.next
    71.                     } else {//移除尾部或者中间
    72.                         let current = this.head,
    73.                         index = 0
    74.                         while (index < position - 1) {
    75.                             current = current.next
    76.                             index++
    77.                         }
    78.                         current.next = current.next.next
    79.                     }
    80.                     this.length--
    81.                 }
    82.             }
    83.  
    84.             indexOf(ele) {
    85.                 let current=this.head,index=0
    86.                 while(index<this.length) {
    87.                     if(current.data==ele) {
    88.                         return index
    89.                     }else {
    90.                         current=current.next
    91.                         index++
    92.                     }
    93.                 }
    94.                 return -1
    95.             }
    96.  
    97.  
    98.             remove(ele) {
    99.                 let index=this.indexOf(ele)
    100.                 this.removeAt(index)
    101.             }
    102.  
    103.             toString(){
    104.                 let current=this.head,index=0,res=""
    105.                 while(index<this.length) {
    106.                     res+="-"+current.data
    107.                     current=current.next
    108.                     index++
    109.                 }
    110.                 return res.slice(1)
    111.             }
    112.         }
    113.         let list = new LinkList();
    114.         for (let i = 0; i < 5; i++) {
    115.             list.append(i)
    116.         }
    117.         console.log(list.toString()); //0-1-2-3-4

    五、完整代码

    1. // 封装链表的构造函数
    2. function LinkedList() {
    3.     // 封装一个Node类, 用于保存每个节点信息
    4.     function Node(element) {
    5.         this.element = element
    6.         this.next = null
    7.     }
    8.  
    9.     // 链表中的属性
    10.     this.length = 0
    11.     this.head = null
    12.  
    13.     // 链表尾部追加元素方法
    14.     LinkedList.prototype.append = function (element) {
    15.         // 1.根据新元素创建节点
    16.         var newNode = new Node(element)
    17.  
    18.         // 2.判断原来链表是否为空
    19.         if (this.head === null) { // 链表尾空
    20.             this.head = newNode
    21.         } else { // 链表不为空
    22.             // 2.1.定义变量, 保存当前找到的节点
    23.             var current = this.head
    24.             while (current.next) {
    25.                 current = current.next
    26.             }
    27.  
    28.             // 2.2.找到最后一项, 将其next赋值为node
    29.             current.next = newNode
    30.         }
    31.  
    32.         // 3.链表长度增加1
    33.         this.length++
    34.     }
    35.  
    36.     // 链表的toString方法
    37.     LinkedList.prototype.toString = function () {
    38.         // 1.定义两个变量
    39.         var current = this.head
    40.         var listString = ""
    41.  
    42.         // 2.循环获取链表中所有的元素
    43.         while (current) {
    44.             listString += "," + current.element
    45.             current = current.next
    46.         }
    47.  
    48.         // 3.返回最终结果
    49.         return listString.slice(1)
    50.     }
    51.  
    52.     // 根据下标删除元素
    53.     LinkedList.prototype.insert = function (position, element) {
    54.         // 1.检测越界问题: 越界插入失败
    55.         if (position < 0 || position > this.length) return false
    56.  
    57.         // 2.定义变量, 保存信息
    58.         var newNode = new Node(element)
    59.         var current = this.head
    60.         var previous = null
    61.         index = 0
    62.  
    63.         // 3.判断是否列表是否在第一个位置插入
    64.         if (position == 0) {
    65.             newNode.next = current
    66.             this.head = newNode
    67.         } else {
    68.             while (index++ < position) {
    69.                 previous = current
    70.                 current = current.next
    71.             }
    72.  
    73.             newNode.next = current
    74.             previous.next = newNode
    75.         }
    76.  
    77.         // 4.length+1
    78.         this.length++
    79.  
    80.         return true
    81.     }
    82.  
    83.     // 根据位置移除节点
    84.     LinkedList.prototype.removeAt = function (position) {
    85.         // 1.检测越界问题: 越界移除失败, 返回null
    86.         if (position < 0 || position >= this.length) return null
    87.  
    88.         // 2.定义变量, 保存信息
    89.         var current = this.head
    90.         var previous = null
    91.         var index = 0
    92.  
    93.         // 3.判断是否是移除第一项
    94.         if (position === 0) {
    95.             this.head = current.next
    96.         } else {
    97.             while (index++ < position) {
    98.                 previous = current
    99.                 current = current.next
    100.             }
    101.  
    102.             previous.next = current.next
    103.         }
    104.  
    105.         // 4.length-1
    106.         this.length--
    107.  
    108.         // 5.返回移除的数据
    109.         return current.element
    110.     }
    111.  
    112.     // 根据元素获取链表中的位置
    113.     LinkedList.prototype.indexOf = function (element) {
    114.         // 1.定义变量, 保存信息
    115.         var current = this.head
    116.         index = 0
    117.  
    118.         // 2.找到元素所在的位置
    119.         while (current) {
    120.             if (current.element === element) {
    121.                 return index
    122.             }
    123.             index++
    124.             current = current.next
    125.         }
    126.  
    127.         // 3.来到这个位置, 说明没有找到, 则返回-1
    128.         return -1
    129.     }
    130.  
    131.     // 根据元素删除信息
    132.     LinkedList.prototype.remove = function (element) {
    133.         var index = this.indexOf(element)
    134.         return this.removeAt(index)
    135.     }
    136.  
    137.     // 判断链表是否为空
    138.     LinkedList.prototype.isEmpty = function () {
    139.         return this.length == 0
    140.     }
    141.  
    142.     // 获取链表的长度
    143.     LinkedList.prototype.size = function () {
    144.         return this.length
    145.     }
    146.  
    147.     // 获取第一个节点
    148.     LinkedList.prototype.getFirst = function () {
    149.         return this.head.element
    150.     }
    151. }
  • 相关阅读:
    教你快速搭建微服务环境
    PMP每日一练 | 考试不迷路-8.4（包含敏捷+多选）
    【LLM】基于LLM的agent应用（上）
    实现数组的扁平化
    [Python] 字符串操作及方法总结
    SpringBoot基础篇学习笔记
    依赖注入有几种实现方式？
    数据库技术基础--关系数据库
    如何干涉MySQL优化器使用hash join
    将.py文件转化为.exe文件
  • 原文地址：https://blog.csdn.net/qq_52301431/article/details/126471959