2021 / 08 / 30

Typescript实现各种链表结构

本文字数: 5976阅读时间: 14分钟

单向链表

最先开始的肯定是单向链表的实现, 它包含两个域,一个信息域和一个指针域。这个链接指向列表中的下一个节点,而最后一个节点则指向一个空值。

一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接[ 一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接 ]

然后我参照了一下知乎的实现,把需要实现的方法列了一下:

  • // find(item) // 在单链表中寻找item元素 ✅
  • // insert(item, element); // 向单链表中插入元素 ✅
  • // remove(item); // 在单链表中删除一个节点 ✅
  • // append(element); // 在单链表的尾部添加元素 ✅
  • // findLast(); // 获取单链表的最后一个节点 ✅
  • // isEmpty(); // 判断单链表是否为空 ✅
  • // show(); // 显示当前节点 ✅
  • // getLength(); // 获取单链表的长度 ✅
  • // display(); // 单链表的遍历显示 ✅
  • // clear(); // 清空单链表 ✅

基本上跟着需求一个一个实现就行了,唯一要注意的点就是删除链表节点的时候要接上被删除的节点的下一个节点,即head -> 1 -> 2 -> 3 => head -> 2 -> 3


class LNode {
    data: string
    next: LNode | null
    constructor(data: string, nextNode: LNode | null = null) {
        this.data = data
        this.next = nextNode
    }
}

class SinglyLinkedList {
    head: LNode
    length: number
    constructor() {
        this.head = new LNode('head')
        this.length = 1
    }
    find(item: string) {
        let currentNode = this.head
        while (currentNode.next && currentNode.data !== item) {
            currentNode = currentNode.next
        }
        return currentNode
    }
    insert(item: string, element: string) {
        const currentNode = this.find(item)
        const newNode = new LNode(element, currentNode.next)
        currentNode.next = newNode
        this.length += 1
    }
    remove(item: string) {
        // protect head
        if (item === 'head') {
            return
        }
        let currentNode = this.head
        while (currentNode.next) {
            if (currentNode.next.data === item) {
                this.length -= 1
                currentNode.next = currentNode.next.next // 1->2->3 => 1->3
                return
            }
            currentNode = currentNode.next
        }
    }
    display() {
        let showText = this.head.data
        let currentNode = this.head
        while (currentNode.next) {
            currentNode = currentNode.next
            showText += ` -> ${currentNode.data}`
        }
        console.log(showText)
    }
    clear() {
        this.head = new LNode('head')
        this.length = 1
    }
    getLength() {
        console.log(this.length - 1)
        return this.length - 1
    }
    findLast() {
        let currentNode = this.head
        while (currentNode.next) {
            currentNode = currentNode.next
        }
        return currentNode
    }
    isEmpty() {
        return this.length === 1 // only head
    }
    append(element: string) {
        const lastNode = this.findLast()
        lastNode.next = new LNode(element)
        this.length += 1
    }
}
const list = new SinglyLinkedList()
const findNode = list.find('head')
list.insert('head', '1')
list.insert('1', '2')
list.insert('2', '3')
list.insert('3', '4')
list.append('5')
list.remove('2')
list.remove('22') // remove error item
list.getLength()
list.display()
list.clear()
list.append('new 1')
list.append('new 2')
list.insert('head', 'berfore 1')
list.insert('new 1', 'berfore 2')
list.getLength()
list.display()

双向链表

首先是从wiki偷来的结构图,对比单向链表多了向前的节点。

一个双向链表有三个整数值: 数值, 向后的节点链接, 向前的节点链接[ 一个双向链表有三个整数值: 数值, 向后的节点链接, 向前的节点链接 ]

它对比单向链表其实也只需要在插入和删除的时候做一下处理,相比于单向列表,删除变得更容易了, 因为很简单,直接丢完整的代码。

class LNode {
    data: string
    next: LNode | null
    prev: LNode | null = null
    constructor(data: string, nextNode: LNode | null = null) {
        this.data = data
        this.next = nextNode
    }
}

class DoublyLinkedList {
    head: LNode
    length: number
    constructor() {
        this.head = new LNode('head')
        this.length = 1
    }
    append(element: string) {
        const lastNode = this.findLast()
        lastNode.next = new LNode(element)
        this.length += 1
    }
    find(item: string) {
        let currentNode = this.head
        while (currentNode.next && currentNode.data !== item) {
            currentNode = currentNode.next
        }
        return currentNode
    }
    insert(item: string, element: string) {
        const currentNode = this.find(item)
        const newNode = new LNode(element, currentNode.next, currentNode)
        if (currentNode.next) {
          currentNode.next.prev = newNode
        }
        currentNode.next = newNode
        this.length += 1
    }
    remove(item: string) {
        // protect head
        if (item === 'head') {
            return
        }
        let currentNode = this.head
        while (currentNode.next) {
            if (currentNode.next.data === item) {
                this.length -= 1
                currentNode.next = currentNode.next.next
                if (currentNode.next) {
                  currentNode.next.prev = currentNode
                }
                return
            }
            currentNode = currentNode.next
        }
    }
    display() {
        let showText = this.head.data
        let currentNode = this.head
        while (currentNode.next) {
            currentNode = currentNode.next
            showText += ` -> ${currentNode.data}`
        }
        console.log(showText)
    }
    clear() {
        this.head = new LNode('head')
        this.length = 1
    }
    getLength() {
        console.log(this.length - 1)
        return this.length - 1
    }
    findLast() {
        let currentNode = this.head
        while (currentNode.next) {
            currentNode = currentNode.next
        }
        return currentNode
    }
    isEmpty() {
        return this.length === 1 // only head
    }
}
const list = new DoublyLinkedList()
const findNode = list.find('head')
list.insert('head', '1')
list.insert('1', '2')
list.insert('2', '3')
list.insert('3', '4')
list.append('5')
list.remove('2')
list.remove('22') // remove error item
list.getLength()
list.display()
list.clear()
list.append('new 1')
list.append('new 2')
list.insert('head', 'berfore 1')
list.insert('new 1', 'berfore 2')
list.getLength()
list.display()
更多阅读