JS数据结构与算法之链表结构

谁践踏了优雅 2024-03-25 07:32 31阅读 0赞

### 认识链表结构 ###

#### 相对于数组，链表的优点 ####

*  内存空间不是必须连续的，可以充分利用计算机发内存实现灵活的内存动态管理

*  链表不必在创建时就确定大小并且大小可以无限的延伸下去

*  链表在插入和删除数据时时间复杂度可以达到O（1）相对数组效率高很多

#### 相对于数组，链表的缺点 ####

*  链表访问任何一个位置的元素都需要从头开始访问无法跳过第一个元素访问任何一个元素

*  无法通过下标直接访问元素需要从头一个个访问直到找到对应元素

*  虽然可以轻松地到达**下一个节点**，但是回到**前一个节点**是很难的

链表和数组的**实现机制完全不同**。链表的每个元素由一个存储**元素本身的节点**和一个**指向下一个元素的引用**（有的语言称为指针或连接）组成。类似于火车头，一节车厢载着乘客（数据），通过节点连接另一节车厢。

![7fc79540dc99300fcefb1e6db0ee0d11.png][]

*  head属性指向链表的第一个节点；

*  链表中的最后一个节点指向null；

*  当链表中一个节点也没有的时候，head直接指向null；

#### **链表中的常见操作** ####

*  append（element）：向链表尾部添加一个新的项；

*  insert（position，element）：向链表的特定位置插入一个新的项；

*  get（position）：获取对应位置的元素；

*  indexOf（element）：返回元素在链表中的索引。如果链表中没有该元素就返回-1；

*  update（position，element）：修改某个位置的元素；

*  removeAt（position）：从链表的特定位置移除一项；

*  remove（element）：从链表中移除一项；

*  isEmpty（）：如果链表中不包含任何元素，返回trun，如果链表长度大于0则返回false；

*  size（）：返回链表包含的元素个数，与数组的length属性类似；

*  toString（）：由于链表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值；

![4506570df5c79c57a2ddefa8c93771c5.png][]

position的值一般表示position所指位置的下一个节点。当position的值与index的值相等时，比如position = index = 1，那么它们都表示Node2。

### js封装单向链表类 ###

#### 创建单项链表类 ####

先创建单向链表类Linklist，并添加基本属性，再实现单向链表的常用方法

// 封装单向链表类
        function LinkList(){
          // 封装一个内部类：节点类
          function Node(data){
            this.data = data;
            this.next = null;
          }
    
          // 属性
          // 属性head指向链表的第一个节点
          this.head = null;
          this.length = 0;
          }

#### **append(element)追加方法** ####

// 一.实现append方法
          LinkList.prototype.append = data => {
            //1.创建新节点
            let newNode = new Node(data)
    
            //2.添加新节点
            //情况1：判断是否添加的是第一个节点
            if(this.length == 0){
              this.head = newNode
            //情况2：节点数大于1，在链表的最后添加新节点  
            }else {              
              //让变量current指向第一个节点
              let current = this.head
              //当current.next(下一个节点不为空)不为空时，一直循环，直到current指向最后一个节点
              while (current.next){
                current = current.next
              }
              // 最后节点的next指向新的节点
              current.next = newNode
            }
            //3.添加完新结点之后length+1
            this.length += 1
          }

测试代码

//测试代码
        //1.创建LinkList
        let list = new LinkList()
        
        //2.测试append方法
        list.append('aaa')
        list.append('bbb')
        list.append('ccc')
        console.log(list);

过程详解

首先让current指向第一个节点：

![f03956ed4040ad85621f1972b221ec10.png][]

通过while循环使current指向最后一个节点，最后通过current.next = newNode，让最后一个节点指向新节点newNode

![0d8ed8560276d2cba1a80981b032d0b0.png][]

#### **toString()** ####

// 实现toString方法
          LinkList.prototype.toString = () => {
            // 1.定义变量
            let current = this.head
            let listString = ""
    
            // 2.循环获取一个个的节点
            while(current){ 
              listString += current.data + " "
              current = current.next//千万不要忘了拼接完一个节点数据之后，让current指向下一个节点
            }
            return  listString
          }

测试代码

//测试代码
        //1.创建LinkList
        let list = new LinkList()
        
        //2.插入数据
        list.append('aaa')
        list.append('bbb')
        list.append('ccc')
        
        //3.测试toString方法
        console.log(list.toString());

#### **insert(position,element)** ####

// 实现insert方法
          LinkList.prototype.insert = (position, data) => {
          //理解positon的含义：position=0表示新界点插入后要成为第1个节点，
          //position=2表示新界点插入后要成为第3个节点
          //1.对position进行越界判断:要求传入的position不能是负数且不能超过LinkList的length
            if(position < 0 || position > this.length){
              return false
            }
            //2.根据data创建newNode
            let newNode = new Node(data)
    
            //3.插入新节点
            //情况1：插入位置position=0
            if(position == 0){
              // 让新节点指向第一个节点
              newNode.next = this.head
              // 让head指向新节点
              this.head = newNode
            //情况2：插入位置position>0(该情况包含position=length)
            } else{
              let index = 0
              let previous = null
              let current = this.head
              //步骤1：通过while循环使变量current指向position位置的后一个节点(注意while循环的写法)
              while(index++ < position){
              //步骤2：在current指向下一个节点之前，让previous指向current当前指向的节点
                previous = current
                current = current.next
              }
              // 步骤3：通过变量current(此时current已经指向position位置的后一个节点)，使newNode指向position位置的后一个节点
              newNode.next = current
              //步骤4：通过变量previous，使position位置的前一个节点指向newNode
              previous.next = newNode
              /*
                启示：
                1.我们无法直接操作链表中的节点，但是可以通过变量指向这些节点，以此间接地操作节点(替身使者)；
                比如current指向节点3，想要节点3指向节点4只需要：current.next = 4即可。
                2.两个节点间是双向的，想要节点2的前一个节点为节点1，可以通过：1.next=2，来实现；
              */
            }
            //4.新节点插入后要length+1
            this.length += 1;
    
            return true
          }

测试代码

//测试代码
        //1.创建LinkList
        let list = new LinkList()
        
        //2.插入数据
        list.append('aaa')
        list.append('bbb')
        list.append('ccc')
        
        //3.测试insert方法
        list.insert(0, '在链表最前面插入节点');
        list.insert(2, '在链表中第二个节点后插入节点');
        list.insert(5, '在链表最后插入节点');
        alert(list);
        console.log(list);

**过程详解：**

inset方法实现的过程：根据插入节点位置的不同可分为多种情况：

**情况1：position = 0**：

通过： newNode.next = this.head，建立连接1；

通过： this.head = newNode，建立连接2；（不能先建立连接2，否则this.head不再指向Node1）

![8b3cfc69dfe2006026008af877b6238f.png][]

**情况2：position > 0**：

首先定义两个变量previous和curent分别指向需要插入位置pos = X的前一个节点和后一个节点；

然后，通过：newNode.next = current，改变指向3；

最后，通过：previous.next = newNode，改变指向4；

![9cfbabefeef7a14064c38ea1a3dc4c73.png][]

**情况2的特殊情形：position = length**：

情况2也包含了pos = length的情况，该情况下current和newNode.next都指向null；建立连接3和连接4的方式与情况2相同。

![4c86a2ddd840d813a844ea3f6bb963fc.png][]

#### **get(position)** ####

//实现get方法
          LinkList.prototype.get = (position) => {
            //1.越界判断
            // 当position = length时，取到的是null所以0 =< position < length
            if(position < 0 || position >= this.length){
              return null
            }
            //2.获取指定的positon位置的后一个节点的data
            //同样使用一个变量间接操作节点
            let current = this.head
            let index = 0
            while(index++ < position){
              current = current.next
            }
            return current.data
          }

测试代码

//测试代码
        //1.创建LinkList
        let list = new LinkList()
        
        //2.插入数据
        list.append('aaa')
        list.append('bbb')
        list.append('ccc')    
    
        //3.测试get方法
        console.log(list.get(0));
        console.log(list.get(1));

**过程详解：**

get方法的实现过程：以获取position = 2为例，如下图所示：

首先使current指向第一个节点，此时index=0；

![b92c22f9319c769a6d125085af72ad87.png][]

通过while循环使current循环指向下一个节点，注意循环终止的条件index++ < position，即当index=position时停止循环，此时循环了1次，current指向第二个节点(Node2)，最后通过current.data返回Node2节点的数据；

![02a1a6b56fa9a9e0aeeba8bdec1ef0e3.png][]

#### **indexOf(element)** ####

//实现indexOf方法
          LinkList.prototype.indexOf = data => {
            //1.定义变量
            let current = this.head
            let index = 0
    
            //2.开始查找:只要current不指向null就一直循环
            while(current){
              if(current.data == data){
                return index
              }
              current = current.next
              index += 1
            } 
    
            //3.遍历完链表没有找到，返回-1
            return -1
          }

测试代码

//测试代码
        //1.创建LinkList
        let list = new LinkList()
        
        //2.插入数据
        list.append('aaa')
        list.append('bbb')
        list.append('ccc')    
        
        //3.测试indexOf方法
        console.log(list.indexOf('aaa'));
        console.log(list.indexOf('ccc'));

**过程详解：**

indexOf方法的实现过程：

使用变量current记录当前指向的节点，使用变量index记录当前节点的索引值（注意index = node数-1）：

![43a216acab32dfdc3f72d05893314b4d.png][]

#### **update(position,element)** ####

//实现update方法
          LinkList.prototype.update = (position, newData) => {
            //1.越界判断
            //因为被修改的节点不能为null，所以position不能等于length
            if(position < 0 || position >= this.length){
              return false
            }
            //2.查找正确的节点
            let current = this.head
            let index = 0
            while(index++ < position){
              current = current.next
            }
            //3.将position位置的后一个节点的data修改成newData
            current.data = newData
            //返回true表示修改成功
            return true
          }

测试代码

//测试代码
        //1.创建LinkList
        let list = new LinkList()
        
        //2.插入数据
        list.append('aaa')
        list.append('bbb')
        list.append('ccc')    
        
        //3.测试update方法
        list.update(0, '修改第一个节点')
        list.update(1, '修改第二个节点')
        console.log(list);
        console.log(list.update(3, '能修改么'));

#### **removeAt(position)** ####

//实现removeAt方法
          LinkList.prototype.removeAt = position => {
            //1.越界判断
            if (position < 0 || position >= this.length) {//position不能为length
              return null
            }
            //2.删除元素
            //情况1：position = 0时(删除第一个节点)
            let current = this.head
            if (position ==0 ) {
            //情况2：position > 0时
              this.head = this.head.next
            }else{
              let index = 0
              let previous = null
              while (index++ < position) {
                previous = current
                current = current.next
              }
              //循环结束后，current指向position后一个节点，previous指向current前一个节点
              //再使前一个节点的next指向current的next即可
              previous.next = current.next
            }
            //3，length-1
            this.length -= 1
    
            //返回被删除节点的data，为此current定义在最上面
            return current.data
          }

测试代码

//测试代码
        //1.创建LinkList
        let list = new LinkList()
        
        //2.插入数据
        list.append('aaa')
        list.append('bbb')
        list.append('ccc')
      
      //3.测试removeAt方法
        console.log(list.removeAt(0));
        console.log(list.removeAt(0));
        console.log(list);

**过程详解：**

removeAt方法的实现过程：删除节点时存在多种情况：

**情况1：position = 0**，即移除第一个节点（Node1）。

通过：this.head = this.head.next，改变指向1即可；

虽然Node1的next仍指向Node2，但是没有引用指向Node1，则Node1会被垃圾回收器自动回收，所以不用处理Node1指向Node2的引用next。

![d4e6986005e9e19ed7557d0d346fe24b.png][]

**情况2：positon > 0**，比如pos = 2即移除第三个节点（Node3）。

**注意：**position = length时position后一个节点为null不能删除，因此position != length；

首先，定义两个变量previous和curent分别指向需要删除位置pos = x的前一个节点和后一个节点；

然后，通过：previous.next = current.next，改变指向1即可；

随后，没有引用指向Node3，Node3就会被自动回收，至此成功删除Node3 。

![ecb4c411c2c32407df438c8b30692b2b.png][]

#### **remove(element)、isEmpty()、size()** ####

/*-------------其他方法的实现--------------*/
          //一.实现remove方法
          LinkList.prototype.remove = (data) => {
            //1.获取data在列表中的位置
            let position = this.indexOf(data)
            //2.根据位置信息，删除结点
            return this.removeAt(position)
          }
    
          //二.实现isEmpty方法
          LinkList.prototype.isEmpty = () => {
            return this.length == 0
          }
    
          //三.实现size方法
          LinkList.prototype.size = () => {
            return this.length
          }

测试代码

//测试代码
        //1.创建LinkList
        let list = new LinkList()
        
        //2.插入数据
        list.append('aaa')
        list.append('bbb')
        list.append('ccc')
    
    /*---------------其他方法测试----------------*/
          //remove方法
          console.log(list.remove('aaa'));
          console.log(list);
          //isEmpty方法
          console.log(list.isEmpty());
          //size方法
          console.log(list.size());

#### 完整实现 ####

// 封装链表类
        function LinkList(){
          // 封装一个内部类：节点类
          function Node(data){
            this.data = data;
            this.next = null;
          }
    
          // 属性
          // 属性head指向链表的第一个节点
          this.head = null;
          this.length = 0;
    
          // 一.实现append方法
          LinkList.prototype.append = data => {
            //1.创建新节点
            let newNode = new Node(data)
    
            //2.添加新节点
            //情况1：只有一个节点时候
            if(this.length == 0){
              this.head = newNode
            //情况2：节点数大于1，在链表的最后添加新节点  
            }else {              
              //让变量current指向第一个节点
              let current = this.head
              //当current.next(下一个节点不为空)不为空时，一直循环，直到current指向最后一个节点
              while (current.next){
                current = current.next
              }
              // 最后节点的next指向新的节点
              current.next = newNode
            }
            //3.添加完新结点之后length+1
            this.length += 1
          }
    
          // 二.实现toString方法
          LinkList.prototype.toString = () => {
            // 1.定义变量
            let current = this.head
            let listString = ""
    
            // 2.循环获取一个个的节点
            while(current){ 
              listString += current.data + " "
              current = current.next//千万不要忘了拼接完一个节点数据之后，让current指向下一个节点
            }
            return  listString
          }
    
          // 三.实现insert方法
          LinkList.prototype.insert = (position, data) => {
          //理解positon的含义：position=0表示新界点插入后要成为第1个节点，position=2表示新界点插入后要成为第3个节点
            //1.对position进行越界判断:要求传入的position不能是负数且不能超过LinkList的length
            if(position < 0 || position > this.length){
              return false
            }
            //2.根据data创建newNode
            let newNode = new Node(data)
    
            //3.插入新节点
            //情况1：插入位置position=0
            if(position == 0){
              // 让新节点指向第一个节点
              newNode.next = this.head
              // 让head指向新节点
              this.head = newNode
            //情况2：插入位置position>0(该情况包含position=length)
            } else{
              let index = 0
              let previous = null
              let current = this.head
              //步骤1：通过while循环使变量current指向position位置的后一个节点(注意while循环的写法)
              while(index++ < position){
              //步骤2：在current指向下一个节点之前，让previous指向current当前指向的节点
                previous = current
                current = current.next
              }
              // 步骤3：通过变量current(此时current已经指向position位置的后一个节点)，使newNode指向position位置的后一个节点
              newNode.next = current
              //步骤4：通过变量previous，使position位置的前一个节点指向newNode
              previous.next = newNode
              
            //我们无法直接操作链表中的节点，但是可以通过变量指向这些节点，以此间接地操作节点；
            }
            //4.新节点插入后要length+1
            this.length += 1;
    
            return true
          }
    
          //四.实现get方法
          LinkList.prototype.get = (position) => {
            //1.越界判断
            // 当position = length时，取到的是null所以0 =< position < length
            if(position < 0 || position >= this.length){
              return null
            }
            //2.获取指定的positon位置的后一个节点的data
            //同样使用一个变量间接操作节点
            let current = this.head
            let index = 0
            while(index++ < position){
              current = current.next
            }
            return current.data
          }
    
          //五.实现indexOf方法
          LinkList.prototype.indexOf = data => {
            //1.定义变量
            let current = this.head
            let index = 0
    
            //2.开始查找:只要current不指向null就一直循环
            while(current){
              if(current.data == data){
                return index
              }
              current = current.next
              index += 1
            } 
    
            //3.遍历完链表没有找到，返回-1
            return -1
          }
    
          //六.实现update方法
          LinkList.prototype.update = (position, newData) => {
            //1.越界判断
            //因为被修改的节点不能为null，所以position不能等于length
            if(position < 0 || position >= this.length){
              return false
            }
            //2.查找正确的节点
            let current = this.head
            let index = 0
            while(index++ < position){
              current = current.next
            }
            //3.将position位置的后一个节点的data修改成newData
            current.data = newData
            //返回true表示修改成功
            return true
          }
    
          //七.实现removeAt方法
          LinkList.prototype.removeAt = position => {
            //1.越界判断
            if (position < 0 || position >= this.length) {
              return null
            }
            //2.删除元素
            //情况1：position = 0时(删除第一个节点)
            let current = this.head
            if (position ==0 ) {
            //情况2：position > 0时
              this.head = this.head.next
            }else{
              let index = 0
              let previous = null
              while (index++ < position) {
                previous = current
                current = current.next
              }
              //循环结束后，current指向position后一个节点，previous指向current前一个节点
              //再使前一个节点的next指向current的next即可
              previous.next = current.next
            }
            //3，length-1
            this.length -= 1
    
            //返回被删除节点的data，为此current定义在最上面
            return current.data
          }
    
    /*-------------其他方法的实现--------------*/
          //八.实现remove方法
          LinkList.prototype.remove = (data) => {
            //1.获取data在列表中的位置
            let position = this.indexOf(data)
            //2.根据位置信息，删除结点
            return this.removeAt(position)
          }
    
          //九.实现isEmpty方法
          LinkList.prototype.isEmpty = () => {
            return this.length == 0
          }
    
          //十.实现size方法
          LinkList.prototype.size = () => {
            return this.length
          }
        }

[7fc79540dc99300fcefb1e6db0ee0d11.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/3ff18793163443838eb29fc95c851d1b.png
[4506570df5c79c57a2ddefa8c93771c5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/74f359d808c945ca9a072415ff567021.png
[f03956ed4040ad85621f1972b221ec10.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/98dcc47cc9644a459433d51ad19263f6.png
[0d8ed8560276d2cba1a80981b032d0b0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/757f97f1cf724190aff2d01beacb8a14.png
[8b3cfc69dfe2006026008af877b6238f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/ae020e5a7eca4c51b74690349122c98c.png
[9cfbabefeef7a14064c38ea1a3dc4c73.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/369c79e892904879925953bff1d4dfea.png
[4c86a2ddd840d813a844ea3f6bb963fc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/a5d50a696cf24b449a9ce4bcd032bc0e.png
[b92c22f9319c769a6d125085af72ad87.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/987e6c85d9364b5f9c39dfe8f6d02f35.png
[02a1a6b56fa9a9e0aeeba8bdec1ef0e3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/c209deae451f4557b8a7bbbe1fa19367.png
[43a216acab32dfdc3f72d05893314b4d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/14b329db461341379e9376134413ea92.png
[d4e6986005e9e19ed7557d0d346fe24b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/f835af1d42b9404caf2044f9b71e3cfa.png
[ecb4c411c2c32407df438c8b30692b2b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/7322841374b0482fb054bd4f57e11e72.png