为什么是链表？

数组的问题

1.连续内存，超出需扩容

2.开头和中间插入、删除数据的成本很高

特点

1.非连续，通过引用(指针)连接，可以实现内存动态管理

2.插入和删除效率奇高

缺点

1.访问元素效率低，需要从头遍历

实现链表

节点类

链表是由节点组成的，因此我们首先需要一个节点类来能够创建节点，然后再通过链表来管理节点。

节点类的实现

class Node<T>{
    value:T
    next:Node<T> | null = null
    constructor(value:T){
        this.value=value
    }
}

链表类

链表是对节点的管理，因此我们需要封装一系列的方法来对类进行操作

首先每个链表都需要有一个指针执行链表的头结点，通过头结点我们才能够对链表进行访问；初次之后我们最好有一个变量记录链表的长度。

class Linkedlist<T>{
    private head:Node<T> | null = null
    private size:number = 0

    get length(){
        return this.size
    }
}

这是最基础的链表类的结构，然后我们就需要添加一系列的方法来进行操作。

添加节点

一开始链表为空，一切的操作都需要以添加节点为基础，有了节点我们才能进行操作。

1.需要首先判断链表是否为空，如果为空那么添加进去的第一个节点将成为头结点

2.若链表不为空，那就是往链表尾部添加，而我们无法通过索引获取到尾部元素，只能通过遍历每个元素才能找到尾部节点。

    append(value:T){
        // 创建新节点
        const newNode = new Node(value)
        // 链表为空
        if(!this.head) {
            this.head = newNode
        }else{
            let current = this.head
            while(current.next){
                current = current.next
            }
            current.next = newNode
        }
        this.size++  
    }

这段代码的重点在于对链表的遍历，一直循环直到有元素的next指针为空，即找到了尾部节点。因为只有尾部节点的next为空。

我们当然也可以批量创建节点了，手动一个个添加节点实在是太慢了

    // 批量创建节点
    appendArr(arr:T[]){
        // 创建新节点
        arr.forEach(element => {
            this.append(element) 
        });
    }

遍历节点

添加了节点要怎么访问呢？要知道链表是没有索引值的，因此只能从头开始访问去找到对应的节点了。

    traverse(){
        const valuse:T[] = []
        let current = this.head
        while(current){
            valuse.push(current.value)
            current = current.next
        }
        console.log(valuse.join('->'))
        return valuse
    }

核心的逻辑就是通过while遍历链表，知道链表尾部(为空)

插入节点

但是要在某个位置插入一个新的节点呢？因为节点是通过指针进行链接的，因为插入节点的操作主要是通过改变指针的指向进行的。

但是头部插入节点是不同的，因为头部插入节点的话就无序遍历整个链表，而只要将head指针指向该节点即可。

    insert(value:T, position:number):boolean{
        // 越界判断
        if(position < 0 || position > this.size) return false

        const newNode = new Node(value)
        // 在头部插入数据
        if(position === 0){
            newNode.next = this.head
            this.head = newNode
        }else{
            let current = this.head
            let previous:Node<T> | null = null
            let index = 0;
            // 寻找目标节点
            while(index++ < position && current){
                previous = current
                current = current.next
            }
            previous!.next = newNode
            newNode.next = current
        }
        this.size++
        return true

    }

根据索引删除节点

链表本身是不能够通过索引进行插入、删除操作的，但是如果一定要通过索引值进行删除呢？我们已经保存了链表的长度size，可以通过size进行越界判断。而根据索引找到节点，只需要从头指针开始向后遍历找到目标节点，然后通过改变指针来实现删除节点了(其实是将目标节点的前一个节点的next指针改变，使该节点无引用而被自动垃圾回收)

    removeIndex(position:number):T | null{
        // 越界判断
        if(position < 0 || position >= this.size) return null
        let current = this.head
        if(position === 0){
            this.head = current?.next ?? null
        }else{
            let previous : Node<T> | null = null
            let index = 0
            while(index++  < position && current){
                previous = current
                current = current.next
            }
            // 改变指向删除节点
            previous!.next = current?.next ?? null
        }
        
        this.size--;
        return current?.value ?? null
    }

根据值获取对应位置的索引

反过来我们还可以通过节点的值来获取到该节点在链表中的位置

    indexOf(value:T):number{
        let current = this.head
        let index = 0
        while(current){
            if(current.value === value){
                return index
            }
            index++
            current = current.next
        }
        return -1
    }

根据 value 删除节点

有了上面的indexOf函数以后，我们就可以根据value找到对应的节点，然后将其删除

    removeValue(value:T):T | null{
        const index = this.indexOf(value)
        return this.removeIndex(index)
    }

判断链表是否为空

很简单，因为我们维护了size的值

    isEmpty():boolean{
        return this.size === 0
    }

得到对应位置的元素

逻辑上并不难，while循环找到对应节点

    get(position:number):T | null{
        if(position < 0 || position >= this.size) return null
        let index = 0
        let current = this.head
        while(index++  < position){
            current = current?.next ?? null
        }
        return current?.value ?? null
    }

但是我们能够看到像while遍历节点的操作我们做了很多次，因为我们可以将得到某一个节点的操作抽取为一个独立的函数。

函数抽取

    private getNode(position:number):Node<T> |  null {
        let index = 0
        let current = this.head
        while(index++ < position && current){
            current = current.next
        }
        return current
    }

于是像上面的get函数便可以简化为：

    get(position:number):T | null{
        if(position < 0 || position >= this.size) return null
        return this.getNode(position)?.value ?? null
    }

更新节点的值

以及我们可以通过getNode获取到目标节点，然后修改它的值

    update(value:T, position:number):boolean{
        if(position < 0 || position >= this.size) return false
        let current = this.getNode(position)
        current!.value = value
        return  true
    }

测试代码

const list = new Linkedlist();
list.appendArr([1,2,3])
list.traverse() // 1->2->3
list.insert(6, 0) // 头部插入
list.insert(8, 2) // 中间插入
list.insert(10, 5) // 尾部插入
list.traverse() // 6->1->8->2->3->10

list.removeIndex(0)//删除头节点
list.traverse() // 1->8->2->3->10
console.log(list.removeIndex(2))//删除中间节点 2
list.traverse() // 1->8->3->10
console.log(list.get(3))//10

console.log(list.update(100,1)) // true
list.traverse() // 1->100->3->10

console.log(list.indexOf(100)) // 1

console.log(list.removeValue(1)) // 1
list.traverse() // 100->3->10

console.log(list.isEmpty()) // false

实现链表的完整结构

//02.代码优化
// 1.创建node节点类
class Node<T>{
    value:T
    next:Node<T> | null = null
    constructor(value:T){
        this.value=value
    }
}

// 创建 Linkedlist类
class Linkedlist<T>{
    private head:Node<T> | null = null
    private size:number = 0

    get length(){
        return this.size
    }

    // 根据postion获取到对应节点
    private getNode(position:number):Node<T> |  null {
        let index = 0
        let current = this.head
        while(index++ < position && current){
            current = current.next
        }
        return current
    }

    // 添加新节点
    append(value:T){
        // 创建新节点
        const newNode = new Node(value)
        // 链表为空
        if(!this.head) {
            this.head = newNode
        }else{
            let current = this.head
            while(current.next){
                current = current.next
            }
            current.next = newNode
        }
        this.size++  
    }

    // 批量创建节点
    appendArr(arr:T[]){
        // 创建新节点
        arr.forEach(element => {
            this.append(element) 
        });
    }

    // 遍历链表
    traverse(){
        const valuse:T[] = []
        let current = this.head
        while(current){
            valuse.push(current.value)
            current = current.next
        }
        console.log(valuse.join('->'))
        return valuse
    }
    // 插入节点
    insert(value:T, position:number):boolean{
        // 越界判断
        if(position < 0 || position > this.size) return false

        const newNode = new Node(value)
        // 在头部插入数据
        if(position === 0){
            newNode.next = this.head
            this.head = newNode
        }else{
            // 找到前一个节点
            const previous = this.getNode(position-1)
            // 将新节点的next指向previous的下一个节点
            newNode.next = previous?.next ?? null
            // 将previous的next指向新节点
            previous!.next = newNode
            
        }
        this.size++
        return true

    }

    // 根据索引删除节点
    removeIndex(position:number):T | null{
        // 越界判断
        if(position < 0 || position >= this.size) return null
        let current = this.head
        if(position === 0){
            this.head = current?.next ?? null
        }else{
            // 找到前一个节点
            const previous = this.getNode(position-1)
            // 改变指向删除节点
            previous!.next = previous?.next?.next ?? null
        }
        
        this.size--;
        return current?.value ?? null
    }
    // 得到对应位置的元素
    get(position:number):T | null{
        if(position < 0 || position >= this.size) return null
        return this.getNode(position)?.value ?? null
    }
    // 更新节点
    update(value:T, position:number):boolean{
        if(position < 0 || position >= this.size) return false
        let current = this.getNode(position)
        current!.value = value
        return  true
    }
    // 根据值获取对应位置的索引
    indexOf(value:T):number{
        let current = this.head
        let index = 0
        while(current){
            if(current.value === value){
                return index
            }
            index++
            current = current.next
        }
        return -1
    }
    // 根据 value 删除节点
    removeValue(value:T):T | null{
        const index = this.indexOf(value)
        return this.removeIndex(index)
    }

    // 判断链表是否为空
    isEmpty():boolean{
        return this.size === 0
    }
}

const list = new Linkedlist();
list.appendArr([1,2,3])
list.traverse() // 1->2->3
list.insert(6, 0) // 头部插入
list.insert(8, 2) // 中间插入
list.insert(10, 5) // 尾部插入
list.traverse() // 6->1->8->2->3->10

list.removeIndex(0)//删除头节点
list.traverse() // 1->8->2->3->10
console.log(list.removeIndex(2))//删除中间节点 2
list.traverse() // 1->8->3->10
console.log(list.get(3))//10

console.log(list.update(100,1)) // true
list.traverse() // 1->100->3->10

console.log(list.indexOf(100)) // 1

console.log(list.removeValue(1)) // 1
list.traverse() // 100->3->10

console.log(list.isEmpty()) // false

export {}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

链表.md

链表.md

为什么是链表？

数组的问题

特点

缺点

实现链表

节点类

链表类

添加节点

遍历节点

插入节点

根据索引删除节点

根据值获取对应位置的索引

根据 value 删除节点

判断链表是否为空

得到对应位置的元素

函数抽取

更新节点的值

测试代码

实现链表的完整结构

接口的重新设计

Files

链表.md

Latest commit

History

链表.md

File metadata and controls

为什么是链表？

数组的问题

特点

缺点

实现链表

节点类

链表类

添加节点

遍历节点

插入节点

根据索引删除节点

根据值获取对应位置的索引

根据 value 删除节点

判断链表是否为空

得到对应位置的元素

函数抽取

更新节点的值

测试代码

实现链表的完整结构

接口的重新设计