数据结构与算法-线性结构之单链表[三]

Bertha 。 2023-06-22 08:26 29阅读 0赞

### 链表 ###

线性表的存储方式除了前面讨论过的顺序存储结构【逻辑上相邻的元素在内存中存放的位置必然是相邻的】  
  还包括链式存储结构，逻辑上相邻的元素，映射在物理内存里面的地址并不是一定是连续的，是任意摆放的。

比如 学号为 ABCDEF的6个学生：

按照 `***顺序表***`来说，逻辑上他们是相邻的，我们安排他们的座位在教室里面，他们的座位一定是按照这个顺序来的，我们知道了A的位置，那么就一定知道C在A的后面第二个，他们的座位顺序一定是A在B前面，B在C前面，按照顺序相邻排列的。

按照`*** 链表***`来说，逻辑上他们是相邻的，我们安排他们的座位是随意安排，但是A同学记住了他后面是B同学，不管座位怎么安排，我知道了A，我就一定知道了B，存储他们的地址【座位】是随机的。但是我们明确的知道每一个元素的下一个元素是谁，维护这样的链接关系。 只要知道最前面的A元素，那么剩下的全部能够找到，他们的座位顺序是任意的。

--------------------

### 链表的节点 ###

链表的里面元素一般性称之为节点，比如上面的学生称之为一个节点。

节点：节点一般有两个域，`数据域` 和 `指针域` 。

数据域存储是我们这个节点的具体数据，实际情况中可能是基础数据类型，也可能是一个对象，比如我们按照上面的学生来举例，那么数据域里面存储的就是一个Student对象，当然对象里面包含名字学号等等自定义内容了。

指针域存储的是当前节点的下一个节点的存储地址，比如我们A同学的数据域存的是一个Student对象，这个实例的名字是A，学号为001，他的座位号是089，这个指针域存的是B的座位号，比如056。B的座位号在计算机内存里面理解为一个地址即可。当然B的座位号可能是任意的，不管你坐那儿，A的指针域存储了，就一定能找到B。

多个节点通过指针域相连接，构成链表。

### 链表的类型 ###

单链表：节点只有一个指针域，存储了下一个元素的地址。  
双链表：节点有两个指针域，不仅存储了下一个元素的地址，也存储了上一个元素的地址。  
循环链表：首尾相连的链表称之为循环链表。

### 链表的代码定义 ###

在js里面不存在指针概念，不用手动清理内存。GC自动帮我们回收。

咱们按照leetcode对于链表的定义来写,使用ES6的class，val是数据域，next为指针域：

class ListNode{ 
      constructor(val) { 
        this.val = val;
        this.next = null
      }
    }

### 链表的实现方式 ###

这里其实可以跳过，有的情况下我们需要一个辅助节点，来帮助我们统一处理链表里面的元素。

比如上面有ABCDEF6个节点，

实现方式一： 头节点就是A，变量h存储 A的地址即可。

const dataA = { 
        name: 'A',
        no: '001'
       }
       let head = new ListNode(dataA)
       
       const dataB = { 
         name: 'B',
         no: '002'
       }
       let nodeB = new ListNode(dataB)
       head.next = nodeB

实现方式二： 头结点是一个特殊的Node，这个节点只是一个辅助节点，它的next指向真正的存储数据的节点A。

// 这里的数据域存的东西，可以存放任意的特殊字符
       let dummy = new ListNode(null)
       let nodeA = new ListNode({ 
        name: 'A',
        no: '001'
       })
       dummy.next = nodeA

我们就采用第二种，第二种让第一个节点【A节点】和其他节点统一化，每一个存储数据的节点都有前驱，不用做额外的特殊处理。而且楼主在leetcode做题的时候，通常都是加一个辅助节点来消除不一致性。

### 单链表的基本操作 ###

请注意：下面所有的操作，都是基于上面提到的第二种实现方式来做，有一个辅助节点dummy。dummy.next 为真正的存储数据的第一个节点。

> **初始化链表**

function initial() {
            var dummy = new ListNode(null)
            dummy.next = null;
            return dummy
        }

> **判断链表是否为空**

function isEmptyList(l) { 
            return l.next == null
        }

> **销毁链表 ----- 链表销毁后不存在了，所有节点内存释放，再也找不到踪迹。**

因为js里面垃圾回收是自动回收，我们这里模拟一个释放内存的动作，一个delete函数。

function delete(node) { 
            // 释放内存....
        }

function destroy(l) {
           let p = null
           while(l != null) {
              p = l
              l = l.next
              delete(p)
           }
        }

> **清空链表 ----- 只是将数据节点清空了，链表中无存储数据的元素，头结点仍然存在。**

清空链表与销毁链表的区别，可以这样想，A考试作弊，被xx中学开除学籍，这样就是销毁了，A学校里面不在有A的任何信息。 清空链表就是A学生成绩全部作废，但是A仍然在这个学校里面，后续如果需要参加重修课程等，直接去上课就对了，而不用从新初始化【办理入学手续】。

function clear(l) { 
            // let q = null;
            let q = l.next
            let p = null
            while(q != null) { 
                let p = q
                q = q.next
                delete(p)
            }
        }

> **求单链表的表长**

function listLength(l) { 
            let p = l.next;
            let i = 0
            while(p != null) { 
                i++
                p = p.next
            }
            return i
        }

> **取第i个元素**

function getEleByIndex(l, i) { 
            let p = l.next, index = 1
            
            while(p != null ) { 
                if (index++ == i) { 
                    return p
                } 
                p = p.next
            }
            return null
        }
        
        function getEleByIndex(l, i) { 
            let p = l.next, index = 1
            while(p != null && index < i) {  // 等于i的情况循环结束
                p = p.next
                index++
            }
            if (p == null || index > i) return null // 没找到元素
            return p
        }

> **删除第i个元素**

> **删掉单链表中值为val的元素**【没有重复值的情况，移动指针之后直接break就好了】

function deleteNode(l, val) { 
    		let head = l
    		while(l.next != null) { 
    			if (l.next.val === val) { 
    				l.next = l.next.next
    				break
    			}
    		}
    		return head
    	}

> **删掉单链表中值为val的元素**【考虑有重复值的情况】

function deleteNode(l, val) { 
    		let head = l
    		while(l.next != null) { 
    			if (l.next.val === val) { 
    				l.next = l.next.next
    			} else { 
    				l = l.next
    			}
    		}
    		return head
    	}

> **查找数据域为特定值的节点**

// 方法一 提前返回
        funciton getEleByVal(l, data) { 
            let p = l.next
            while( p != null) { 
                if (p.val === data) { 
                    return p
                }
            }
            return null
        }
    
        // 方法二 没有提前返回
        function getEleByVal(l, data) { 
            let p = l.next
            while(p!= null && p.val != data) { 
                p = p.next
            }
            return p
        }

> **查找数据域为特定值的节点**

> **根据数据域的值查找节点在链表中的位置,index**

function getIndexByEleVal(l, data) { 
            let p = l.next
            let index = 1
            while(p != null && data != p.val) { 
                p = p.next
                index++
            }
            if (p == null) return -1 // 没找到返回-1 或者0 ，自定义
            return index
        }

--------------------

后面就是插入删除操作了，这些操作就能体现为什么我们需要一个辅助dummy节点了，消除特殊的第一个节点和最后一个节点与其他普通节点的差异。处理起来更方便

> **在第i个节点前插入一个值(数据域)为e的节点**

// 方法一
        function insert(l, e, i) { 
            // i应该>=1
            // 错误，我们要找的插入位置的前一个节点，明显dummy节点也在范围内
            // let p = l.next, index = 1
            
            let p = l, index = 0;
            let newNode = new ListNode(e)
            while(p != null) { 
                if (index == i - 1) { 
                    // 这里有问题，p就是前一个节点，所以直接t = p.next即可
                    // let t = p.next ? p.next.next : null 
                    
                    let t = p.next
                    p.next = newNodee
                    newNode.next = t
                    
                    // 或者简写版本
                    newNode.next = p.next
                    p.next = newNode
                    return 
                }
                index++
            }
        }
        
        // 方法二 不在while循环里面做操作逻辑
        function insert(l, e, i) { 
            let p = l, index = 0
            // 需要找到插入位置的前一个节点 i-1
            while(p != null && index < i - 1){ 
                p = p.next
                index++
                // 最后一次 index = i-2
                // p = p.next 此时 p节点指向的是第 i-1个节点
            }
            
            if(p == null ||  index > i - 1) return new Error('插入失败') // i大于表长，或者小于1， i< 1, index > i-1 跳出，p =null i > index
            let newNode = new ListNode(e)
            newNode.next = p.next
            p.next = newNode
            
        }

> **给定一个数组，建立一个单链表----头插法**

比如我们的数组为\[‘A’,‘B’,‘C’,‘D’,‘E’\] 头插法就是每次往链表头部插入新的节点，类似于JS数组里面的unshift()方法。

function createList_Head(arr) { 
            let dummy = new ListNode(null);
            dummy.next = null // 默认是空，有一点多余
            let n = arr.length;
            for (let i = n - 1; i >= 0; i++) { 
                let newNode = new ListNode(arr[i])
                newNode.next = dummy.next
                dummy.next = newNode
            }
            return dummy
        }

> **给定一个数组，建立一个单链表----尾插法**

和上面类似

function createList_Tail(arr) { 
            let dummy = new ListNode(null)
            dummy.next = null
            let p = dummy // p为尾指针
            for (let i = 0, j = arr.length; i < j; i++) { 
                let newNode = new ListNode(arr[i])
                newNode.next = null 
                p.next = newNode
                p = p.next
            }
            return dummy
        }

上面的基本操作，时间复杂度都为O(n)