链表数据结构（单链表）

date
Mar 17, 2023
slug
js-linkedList
status
Published
tags
JavaScript数据结构与算法
Linked-List
JavaScript
summary
Linked list data structure init
type
Post

链表数据结构

链表的数据结构如下图所示：
notion image
要表示链表中的第一个以及其他元素，使用Node类表示想要添加的链表中的项。Node类中element属性表示要加入链表元素的值；next属性是指向链表中下一个元素的指针。
class Node{
    constructor(element){
        this.element = element;
        this.next = undefined;
    }
}
创建 LinkedList 类表示链表。count属性用来存储链表中的元素数量，使用内部函数equalsFn自行传入用于比较两个JavaScript对象或值是否相等的自定义函数。equalsFn为后面查找元素的位置使用。
function defaultEquals(a,b){
    return a === b;
}
class LinkedList{
    constructor(equalsFn = defaultEquals){
        this.count = 0;
        this.head = undefined;
        this.equalsFn = equalsFn;
    }
}
LinkedList类方法的职责：
  • push(element)：向链表尾部添加一个新元素。
  • insert(element, position)：向链表的特定位置插入一个新元素。
  • getElementAt(index)：返回链表中特定位置的元素。如果链表中不存在这样的元素， 则返回 undefined。
  • remove(element)：从链表中移除一个元素。
  • indexOf(element)：返回元素在链表中的索引。如果链表中没有该元素则返回-1。
  • removeAt(position)：从链表的特定位置移除一个元素
  • isEmpty()：如果链表中不包含任何元素，返回 true，如果链表长度大于 0则返回 false。
  • size()：返回链表包含的元素个数。
  • toString()：返回表示整个链表的字符串。由于列表项使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString 方法，让其只输出元素的值

向链表尾部添加元素

向LinkedList对象尾部添加一个元素时，有两种情况：
  1. 链表为空，添加的是第一个元素
      2. 当我们创建 LinkedList 对象时，head 会指向 undedined或者是 null。所以，如果 head 元素为 undefined 或 null，就意味着在向链表添加第一个元素。因此要做的就是让 head 元素指向 node 元素，下一个 node 元素会自动成为 undefined
      notion image
  1. 链表不为空，向其追加元素
      2. 要向链表的尾部添加元素，需要找到最后一个元素。当循环链表current.next = undefined/null时到达链表尾部。
push(element){
    const node = new Node(element);
    if(this.head == null){
        this.head = node;
    }else{
        let current = this.head;
        //获取最后一项
        while(current.next != null){
            current = current.next;
        }
        //将其 next 赋为新元素，建立链接
        current.next = node;
    }
    this.count ++;
}
测试添加元素
const list = new LinkedList();list.push(15);list.push(10);

返回一个元素的位置

indexOf方法接收一个元素的值，如果在链表中找到了它，就返回元素的位置，否则返回-1
indexOf(element){
    let current = this.head;
    for(let i = 0; i < this.count && current != null; i++){
        if(this.equalsFn(element,current.element))
            {
                return i;
            }
        current = current.next;
    }
    return -1;
}

从链表中移除元素

从特定的位置移除一个元素

removeAt(index){
    if(index >= 0 && index < this.count){
        let current = this.head;
        if(index == 0){
            //移除第一项
            this.head = current.next;
        }else{
            let previous;
            for(let i = 0; i < index; i++){
                previous = current;
                current = current.next;
            }
            previous.next = current.next;
        }
        this.count --;
        return current.element;
    }
    return undefined;
}
移除第一个元素：
notion image
移除第一个元素之外的其他元素：
notion image

根据元素的值移除元素

首先传入元素的值得到它的位置，调用removeAt方法并传入该位置进行元素的删除。
remove(element){
    const index = this.indexOf(element);
    return this.removeAt(index);
}

查找链表指定位置元素

getElementAt(index){
    if(index >= 0 && index <= this.count){
        let current = this.head;
        for(let i = 0; i < index && current != null; i++)
            {
                current = current.next;
            }
        return current;
    }
    return undefined;
}

在任意位置插入元素

insert(element,index){
    if(index > 0 && index <= this.count){
        const node = new Node(element);
        if(index === 0){//在第一个位置添加
            const current = this.head;
            node.next = current;
            this.head = node;
        }else{
            const previous = this.getElementAt(index - 1);
            const current = previous.next;
            node.next = current;
            previous.next = node; 
       }
        this.count ++;
        return true;
    }
    return false;
}
在第一个位置添加元素
notion image
在其他位置添加元素
notion image

判断链表是否为空、大小以及获取头结点

size(){
    return this.count;
}
isEmpty(){
  return this.size() === 0  
}
getHead(){
    return this.head === null ? undefined : this.head.element;
}

使用链表

接下来我们可以使用创建好的单链表
const linkedList = new LinkedList()
console.log(linkedList.size())          // 0 
console.log(linkedList.isEmpty())       // true
linkedList.push(1)
console.log(linkedList.getHead())       // 1
linkedList.push(3)
linkedList.push(2)
linkedList.push(5)
console.log(linkedList.size())          // 4
let node = linkedList.getElementAt(2)
console.log(node.element)               // 2
console.log(linkedList.indexOf(5))      // 3
console.log(linkedList.indexOf(8))      // -1
console.log(linkedList.insert(9, 1))    // true
console.log(linkedList.toString())      // 1,9,3,2,5
console.log(linkedList.remove(2))       // 2
console.log(linkedList.toString())      // 1,9,3,5
console.log(linkedList.removeAt(2))     // 3
console.log(linkedList.toString())      // 1,9,5
使用的完整代码
class Node{
    constructor(element){
        this.element = element;
        this.next = undefined;
    }
}
function defaultEquals(a,b){
    return a === b;
}
class LinkedList{
    constructor(equalsFn = defaultEquals){
        this.count = 0;
        this.head = undefined;
        this.equalsFn = equalsFn;
    }
    size(){
        return this.count;
    }
    isEmpty(){
      return this.size() === 0  
    }
    getHead(){
        return this.head === null ? undefined : this.head.element;
    }
    push(element){
        const node = new Node(element);
        if(this.head == null){
            this.head = node;
        }else{
            let current = this.head;
            //获取最后一项
            while(current.next != null){
                current = current.next;
            }
            //将其 next 赋为新元素，建立链接
            current.next = node;
        }
        this.count ++;
    }
    indexOf(element){
        let current = this.head;
        for(let i = 0; i < this.count && current != null; i++){
            if(this.equalsFn(element,current.element))
                {
                    return i;
                }
            current = current.next;
        }
        return -1;
    }
    removeAt(index){
        if(index >= 0 && index < this.count){
            let current = this.head;
            if(index == 0){
                //移除第一项
                this.head = current.next;
            }else{
                let previous;
                for(let i = 0; i < index; i++){
                    previous = current;
                    current = current.next;
                }
                previous.next = current.next;
            }
            this.count --;
            return current.element;
        }
        return undefined;
    }
    remove(element){
        const index = this.indexOf(element);
        return this.removeAt(index);
    }
    getElementAt(index){
        if(index >= 0 && index <= this.count){
            let current = this.head;
            for(let i = 0; i < index && current != null; i++)
                {
                    current = current.next;
                }
            return current;
        }
        return undefined;
    }
    insert(element,index){
        if(index > 0 && index <= this.count){
            const node = new Node(element);
            if(index === 0){//在第一个位置添加
                const current = this.head;
                node.next = current;
                this.head = node;
            }else{
                const previous = this.getElementAt(index - 1);
                const current = previous.next;
                node.next = current;
                previous.next = node;
            }
            this.count ++;
            return true;
        }
        return false;
    }
    toString () {
        if (this.count === 0) {
          return ''
        }
        let str = `${this.head.element}`
        let current = this.head.next
        for (let index = 1; index < this.count && current != null; index++) {
          str = `${str},${current.element}`
          current = current.next
        }
        return str
      }
}

const linkedList = new LinkedList()
console.log(linkedList.size())          // 0 
console.log(linkedList.isEmpty())       // true
linkedList.push(1)
console.log(linkedList.getHead())       // 1
linkedList.push(3)
linkedList.push(2)
linkedList.push(5)
console.log(linkedList.size())          // 4
let node = linkedList.getElementAt(2)
console.log(node.element)               // 2
console.log(linkedList.indexOf(5))      // 3
console.log(linkedList.indexOf(8))      // -1
console.log(linkedList.insert(9, 1))    // true
console.log(linkedList.toString())      // 1,9,3,2,5
console.log(linkedList.remove(2))       // 2
console.log(linkedList.toString())      // 1,9,3,5
console.log(linkedList.removeAt(2))     // 3
console.log(linkedList.toString())      // 1,9,5

© shallrise 2025