首页 > 其他分享 >双向链表

双向链表

时间：2022-10-29 15:34:41浏览次数：53  
标签：current 链表 tail 双向 position prev 节点

双向链表

双向链表简介

链表有多种不同的类型，本节介绍双向链表。双向链表和普通链表的区别在于，在链表中， 一个节点只有链向下一个节点的链接；而在双向链表中，链接是双向的：一个链向下一个元素， 另一个链向前一个元素

双向链表的缺点：

  • 每次在插入或删除某个节点时，都需要处理四个引用，而不是两个，实现起来会困难些；
  • 相对于单向链表，所占内存空间更大一些；
  • 但是，相对于双向链表的便利性而言，这些缺点微不足道。

双向链表的结构：

image-20221027193049052

image-20221027193350257

  • 双向链表不仅有head指针指向第一个节点，而且有tail指针指向最后一个节点；
  • 每一个节点由三部分组成：item储存数据、prev指向前一个节点、next指向后一个节点；
  • 双向链表的第一个节点的prev指向null；
  • 双向链表的最后一个节点的next指向null；

双向链表常见的操作（方法）：

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

  • inset（position，data）：向链表的特定位置插入一个新的项；

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

  • indexOf（data）：返回元素在链表中的索引，如果链表中没有元素就返回-1；

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

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

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

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

  • toString（data）：输出链表中字符串的值，参数: 1：正向，-1：反向

  • forwardString（）：返回正向遍历节点字符串形式；

  • backwordString（）：返回反向遍历的节点的字符串形式；

封装双向链表

封装类

// 节点类
class Node {
    constructor(data) {
        this.data = data
        this.prev = null
        this.next = null
    }
}
// 封装双向链表类
class DoubleLinkList {
    constructor() {
        // 属性
        this.head = null
        this.tail = null
        this.length = 0
    }
}

1.append(data)

向尾部添加新节点分为两种情况：

  1. 链表中还没有节点(0节点)
    • 只需要将head和tail都指向新节点
  2. 链表中已存在节点
    • 先将新节点的prev指向tail(最后一个节点)
    • 再将tail(最后一个节点)的next指向新节点
    • 最后将最后一个节点指向新节点
    • image-20221028144200320

代码实现

// 尾部添加一个节点
append(data) {
    // 1.创建节点
    const newNode = new Node(data)
    // 2.判断添加的是否是第一个节点
    if (!this.length) {
        // 是第一个节点
        this.head = newNode
        this.tail = newNode
    } else {
        // 先将新节点的prev指向tail(最后一个节点)
        newNode.prev = this.tail
        // 再将tail(最后一个节点)的next指向新节点
        this.tail.next = newNode
        // 将最后一个节点设置成新节点
        this.tail = newNode
    }
    // 3.长度+1
    this.length += 1
}

测试代码

const dbList = new DoubleLinkList()
dbList.append('aaa')
dbList.append('bbb')
dbList.append('ccc')
console.log(dbList);

image-20221028144554363

2.insert(position, data)

插入一个新节点有多种情况：

  1. 插入的位置为0

    • 分两种情况，一是链表是空，只需要把 head 和 tail 都指向这个新节点

    • 二是链表不为空，把head.prev指向newNode，再将newNode设置为head，当前head.next指向记录的老head

      image-20221028165527826

  2. 插入的位置是最后一个(position === length)

    • 新节点的prev指向tail，tail.next指向新节点，再把tail重新指向新节点

      image-20221028165208013

  3. 插入的位置大于0 且 小于 length

    • 循环找到要插入的位置
      1. current.prev.next = newNode，将newNode设置为当前节点的位置
      2. newNode.prev = current.prev ， 新节点的prev等于当前节点的prev
      3. current.prev = newNode，newNode.next = current，这是互相连接

代码实现

// 指定位置插入一个节点
insert(position, data) {
    // 1.越界判断
    if (position < 0 || position > this.length) return false

    // 2.根据data创建新节点
    const newNode = new Node(data)

    // 3.找到位置并插入
    let current = this.head
    let index = 0
    let prevCurrent = null // 用来记录当前循环的节点的prev
    // 3.1如果插入的时候链表是一个空链表
    if (this.length === 0) {
        this.head = newNode
        this.tail = newNode
        // 3.2如果插入的位置是0
    } else if (position === 0) {
        // 将当前第一个节点的prev指向新节点
        current.prev = newNode
        // 将新节点设置成第一个节点
        this.head = newNode
        // 新节点的next指向记录下来的current
        this.head.next = current
        // 3.3如果插入的位置最后一个（链表的长度）
    } else if (position === this.length) {
        newNode.prev = this.tail
        this.tail.next = newNode
        this.tail = newNode
        // 3.4 插入的位置不是头也不是尾
    } else {
        while (current) {
            if (index === position) {
                current.prev.next = newNode
                newNode.prev = current.prev 
                current.prev = newNode
                newNode.next = current
                break
            }
            index += 1
            current = current.next
        }
    }
    // 4.长度 +1
    this.length += 1
    return newNode
}

代码测试：

const dbList = new DoubleLinkList()
dbList.insert(0, 'aaa')
dbList.insert(0, 'root')
dbList.insert(2, 'bbb')
dbList.insert(1, 'root_son')
console.log(dbList);

image-20221028170708962

3.get(data)

代码实现

// 获取对应位置的元素
get(position) {
    if (position < 0 || position > this.length) return null
    let current = this.head
    let index = 0
    while (current) {
        if (index === position) {
            return current
        }
        index += 1
        current = current.next
    }
    return null
}

如果考虑到性能，当节点过多，从head开始循环貌似不是最优的办法，如果节点很多，我们要找的节点又靠后呢？那将浪费很多性能，解决办法就是判断position的位置距离head和tail哪个近，就从那边循环

  • position < this.length / 2，从head开始遍历
  • position > this.length / 2，从tail开始遍历

优化后的代码：

// 获取对应位置的元素
get(position) {
    if (position < 0 || position > this.length) return null
    if (position < this.length / 2) {
        let index = 0
        let current = this.head
        while (current) {
            if (index === position) {
                return current
            }
            index += 1
            current = current.next
        }
    }else {
        let current = this.tail
        let index = this.length - 1
        while (current) {
            if (index === position) {
                return current
            }
            index -= 1
            current = current.prev
        }
    }
    return null
}

测试代码

const dbList = new DoubleLinkList()
dbList.insert(0, 'aaa')
dbList.insert(0, 'root')
dbList.insert(2, 'bbb')
dbList.insert(1, 'root_son')
console.log(dbList);
console.log(dbList.get(3));

image-20221029131115921

4.indexOf(data)

// 返回元素在链表中的索引
indexOf(data) {
    let index = 0
    let current = this.head
    while (current) {
        if (current.data === data) {
            return index
        }
        current = current.next
        index += 1
    }
    return -1
}

5.update(position, data)

实现代码

// 修改某个位置的元素
update(position, data) {
    // 越界判断
    if (position < 0 || position > this.length - 1) return false
    // 判断position位置距离head和tail哪个近
    if (position < this.length / 2) {
        let index = 0
        let current = this.head
        while (current) {
            if (index === position) {
                current.data = data
                return true
            }
            index += 1
            current = current.next
        }
    } else {
        let index = this.length - 1
        let current = this.tail
        while (current) {
            if (index === position) {
                current.data = data
                return true
            }
            index -= 1
            current = current.prev
        }
    }
}

测试代码

const dbList = new DoubleLinkList()
dbList.insert(0, 'root')
dbList.insert(1, 'root_son')
dbList.insert(2, 'aaa')
dbList.insert(3, 'bbb')
console.log(dbList.update(0, 'root-update')); 
console.log(dbList.update(3, 'bbb-update')); 
console.log(dbList);

image-20221029141437871

6.removeAt(position)

删除一个节点有四种情况：

  1. 只有一个节点的时候，需要把head、tail指向null
  2. 删除第一个节点，head指向this.head.next，再把新head的prev指向null
  3. 删除最后一个节点，tail指向this.tail.prev，再把新tail的next指向null
  4. 删除中间的节点，current.prev.next指向current.next，current.next.prev = current.prev。互相指向，跳过current

实现代码

// 从链表的特定位置移除一项
removeAt(position) {
    // 越界判断
    if (position < 0 || position > this.length - 1) return false
    // 四种情况：1.length===1。 2.移除的是第一个，3.移除的是最后一个，4.非第一个和最后一个
    // 如果length===1
    if (this.length === 1) {
        this.head = null
        this.tail = null
        //移除的是第一个
    } else if (position === 0) {
        this.head = this.head.next
        this.head.prev = null
        // 移除的是最后一个
    } else if (position === this.length - 1) {
        this.tail = this.tail.prev
        this.tail.next = null
    } else {
        // 移除的是中间的
        let index = 0
        let current = this.head
        while (current) {
            if(index === position) {
                current.next.prev = current.prev
                current.prev.next = current.next
            }
            index += 1
            current = current.next
        }
    }
    // 长度改变 -1
    this.length -= 1
    return true
}

测试代码

const dbList = new DoubleLinkList()
dbList.insert(0, 'AAA')
dbList.insert(1, 'BBB')
dbList.insert(2, 'CCC')
dbList.insert(3, 'DDD')
dbList.removeAt(1)
console.log(dbList);

image-20221029150445120

7.isEmpty()

// 链表中包不包含任何元素
isEmpty() {
    return !!this.length
}

8.size()

// 返回链表包含的元素个数
size() {
    return this.length
}

9.toString()

// 输出链表中字符串的值，参数: 1：正向，-1：反向
toString(data) {
    if(data === 1) return this.forwardString()
    if(data === -1) return this.backwordString()
}

10.forwardString()

// 返回正向遍历节点字符串形式
forwardString() {
    let res = ''
    let current = this.head
    while (current) {
        res += current.data + ' '
        current = current.next
    }
    return res
}

11.backwordString()

// 返回反向遍历的节点的字符串形式
backwordString() {
    let res = ''
    let current = this.tail
    while (current) {
        res += current.data + ' '
        current = current.prev
    }
    return res
}

整体代码

// 节点类
class Node {
    constructor(data) {
        this.data = data
        this.prev = null
        this.next = null
    }
}
// 封装双向链表类
class DoubleLinkList {
    constructor() {
        // 属性
        this.head = null
        this.tail = null
        this.length = 0
    }
    // 尾部添加一个节点
    append(data) {
        // 1.创建节点
        const newNode = new Node(data)
        // 2.判断添加的是否是第一个节点
        if (!this.length) {
            // 是第一个节点
            this.head = newNode
            this.tail = newNode
        } else {
            // 先将新节点的prev指向tail(最后一个节点)
            newNode.prev = this.tail
            // 再将tail(最后一个节点)的next指向新节点
            this.tail.next = newNode
            // 将最后一个节点设置成新节点
            this.tail = newNode
        }
        // 3.长度+1
        this.length += 1
    }
    // 返回正向遍历节点字符串形式
    forwardString() {
        let res = ''
        let current = this.head
        while (current) {
            res += current.data + ' '
            current = current.next
        }
        return res
    }
    // 返回反向遍历的节点的字符串形式
    backwordString() {
        let res = ''
        let current = this.tail
        while (current) {
            res += current.data + ' '
            current = current.prev
        }
        return res
    }
    // 指定位置插入一个节点
    insert(position, data) {
        // 1.越界判断
        if (position < 0 || position > this.length) return false

        // 2.根据data创建新节点
        const newNode = new Node(data)

        // 3.找到位置并插入
        let current = this.head
        let index = 0
        let prevCurrent = null // 用来记录当前循环的节点的prev
        // 3.1如果插入的时候链表是一个空链表
        if (this.length === 0) {
            this.head = newNode
            this.tail = newNode
            // 3.2如果插入的位置是0
        } else if (position === 0) {
            // 将当前第一个节点的prev指向新节点
            current.prev = newNode
            // 将新节点设置成第一个节点
            this.head = newNode
            // 新节点的next指向记录下来的current
            this.head.next = current
            // 3.3如果插入的位置最后一个（链表的长度）
        } else if (position === this.length) {
            newNode.prev = this.tail
            this.tail.next = newNode
            this.tail = newNode
            // 3.4 插入的位置不是头也不是尾
        } else {
            while (current) {
                if (index === position) {
                    current.prev.next = newNode
                    newNode.prev = current.prev
                    current.prev = newNode
                    newNode.next = current
                    break
                }
                index += 1
                current = current.next
            }
        }
        // 4.长度 +1
        this.length += 1
        return newNode
    }
    // 获取对应位置的元素
    get(position) {
        if (position < 0 || position > this.length) return null
        if (position < this.length / 2) {
            let index = 0
            let current = this.head
            while (current) {
                if (index === position) {
                    return current
                }
                index += 1
                current = current.next
            }
        } else {
            let current = this.tail
            let index = this.length - 1
            while (current) {
                if (index === position) {
                    return current
                }
                index -= 1
                current = current.prev
            }
        }
        return null
    }
    // 返回元素在链表中的索引
    indexOf(data) {
        let index = 0
        let current = this.head
        while (current) {
            if (current.data === data) {
                return index
            }
            current = current.next
            index += 1
        }
        return -1
    }
    // 修改某个位置的元素
    update(position, data) {
        // 越界判断
        if (position < 0 || position > this.length - 1) return false
        // 判断position位置距离head和tail哪个近
        if (position < this.length / 2) {
            let index = 0
            let current = this.head
            while (current) {
                if (index === position) {
                    current.data = data
                    return true
                }
                index += 1
                current = current.next
            }
        } else {
            let index = this.length - 1
            let current = this.tail
            while (current) {
                if (index === position) {
                    current.data = data
                    return true
                }
                index -= 1
                current = current.prev
            }
        }
    }
    // 从链表的特定位置移除一项
    removeAt(position) {
        // 越界判断
        if (position < 0 || position > this.length - 1) return false
        // 四种情况：1.length===1。 2.移除的是第一个，3.移除的是最后一个，4.非第一个和最后一个
        // 如果length===1
        if (this.length === 1) {
            this.head = null
            this.tail = null
            //移除的是第一个
        } else if (position === 0) {
            this.head = this.head.next
            this.head.prev = null
            // 移除的是最后一个
        } else if (position === this.length - 1) {
            this.tail = this.tail.prev
            this.tail.next = null
        } else {
            // 移除的是中间的
            let index = 0
            let current = this.head
            while (current) {
                if(index === position) {
                    current.next.prev = current.prev
                    current.prev.next = current.next
                }
                index += 1
                current = current.next
            }
        }
        // 长度改变 -1
        this.length -= 1
        return true
    }
    // 链表中包不包含任何元素
    isEmpty() {
        return !!this.length
    }
    // 返回链表包含的元素个数
    size() {
        return this.length
    }
    // 输出链表中字符串的值，参数: 1：正向，-1：反向
    toString(data) {
        if(data === 1) return this.forwardString()
        if(data === -1) return this.backwordString()
    }
}

标签：current,链表,tail,双向,position,prev,节点
From： https://www.cnblogs.com/codehaoran/p/16838816.html

相关文章

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99