快捷導(dǎo)航

JS實現(xiàn)鏈表數(shù)據(jù)結(jié)構(gòu)的代碼詳解

更新時間：2024年01月22日 08:55:46 作者：翰玥

很多前端的同學(xué)對數(shù)據(jù)結(jié)構(gòu)和算法這塊沒有太多的概念,很多l(xiāng)eetcode的題目看不懂,有時候可能看了題解也不知道是什么意思,這篇文章咱們來簡單的談一談鏈表,文中給大家介紹了JS實現(xiàn)鏈表數(shù)據(jù)結(jié)構(gòu)的示例代碼,需要的朋友可以參考下

什么是鏈表

定義：鏈表是一種遞歸的數(shù)據(jù)結(jié)構(gòu)，它或者空（null）,或者是指向一個結(jié)點（node）的引用，該結(jié)點含有一個泛型的元素和一個指向另一條鏈表的引用。（摘抄自《算法第四版》）不是很好的理解?下面來簡單的解釋一下。

數(shù)組大家肯定都知道。我們想要存儲多個元素的時候，數(shù)組可能是比較常見的一種數(shù)據(jù)結(jié)構(gòu)。但是不知道大家有沒有考慮過這一點，數(shù)組的大小是固定的，如果想要給數(shù)組中隨意的插入或者移除元素的時候，則需要移動其他的元素，那么成本是很高的。

而鏈表是有序的元素集合，與數(shù)組不同的是，鏈表中的元素在內(nèi)存中并不是連續(xù)放置的。每個元素由一個存儲元素本身的節(jié)點和一個指向下一個元素的引用（也稱指針或鏈接）組成。那么鏈表相對于數(shù)組而言它的好處在于，添加或者移除元素的時候，不需要移動其他的元素。

那么再來說說查找，數(shù)組中可以通過索引直接訪問任何位置的元素，但是鏈表則需要從起點開始迭代鏈表直到找到要查找的元素。下面我們用一張圖來標(biāo)示鏈表：

JS實現(xiàn)一個鏈表

下面我們用js實現(xiàn)一個鏈表大家在刷leetcode鏈表的題目的時候，是不是都會看到這樣的代碼

這個其實就是創(chuàng)建鏈表每個節(jié)點的構(gòu)造函數(shù)。這里我們用類來實現(xiàn)

Node類

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

創(chuàng)建鏈表類

class LinkNodeList {
  constructor() {
    this.head = null;
    this.count = 0;
  }
}

head表示頭節(jié)點，count表示鏈表節(jié)點個數(shù)。我們需要實現(xiàn)哪些方法呢？

push(element)：向鏈表尾部添加一個新元素。
insert(element, position)：向鏈表的特定位置插入一個新元素。
getVal(index)：返回鏈表中特定位置的元素。如果鏈表中不存在這樣的元素，則返回undefined。
remove(position)：從鏈表的特定位置移除一個元素。
isEmpty()：如果鏈表中不包含任何元素，返回true，如果鏈表長度大于0則返回false。
size()：返回鏈表包含的元素個數(shù)，與數(shù)組的length屬性類似。
toString()：返回表示整個鏈表的字符串。

size

class LinkNodeList {
  constructor() {
    this.head = null;
    this.count = 0;
  }
  ···
  size() {
        return this.count;
  }
  ···
}

用count記錄節(jié)點個數(shù)，直接返回count即可

isEmpty

class LinkNodeList {
  constructor() {
    this.head = null;
    this.count = 0;
  }
  ···
  isEmpty() {
        return this.size() === 0;
  }
  ···
}

直接判斷size 是否為0即可

push

向鏈表尾部添加一個新元素。

class LinkNodeList {
  constructor() {
    this.head = null;
    this.count = 0;
  }
  ···
  push(element) {
    const node = new Node(element);
    
    if (this.head === null) {
        this.head = node;
    } else {
        let current; = this.head;
        while (current.next) {
            current = current.next;
        }
        current.next = node;
    }
    this.count++;
  }
  ···
}

如果想鏈表的尾部添加一個元素，那么首先需要通過上面實現(xiàn)的Node類來創(chuàng)建一個節(jié)點。如果當(dāng)前的head還不存在，則說明當(dāng)前的鏈表還是一個空，所以直接將head節(jié)點賦值即可。否則就找到鏈表的最后一個節(jié)點，將它的next指向新push的節(jié)點即可。并且將count增加

getVal

返回鏈表中特定位置的元素

class LinkNodeList {
  constructor() {
    this.head = null;
    this.count = 0;
  }
  ···
  getVal(index) {
    if (index > 0 && index <= this.count) {
        let node = this.head;
        for (let i = 0; i < index; i++) {
                node = node.next;
        }
        return node;
    }
    return undefined;
   }
  ···
}

給getVal傳入我們想要查找的位置，首先判斷要查找的位置是否存在，如果不存在則直接返回undefined.

存在的話，則從頭節(jié)點開始循環(huán)查找,直到找到目標(biāo)index。結(jié)束循環(huán)時，node元素就是index位置元素的引用。

insert(element, position)

向鏈表的特定位置插入一個新元素。

class LinkNodeList {
  constructor() {
    this.head = null;
    this.count = 0;
  }
  ···
  insert(ele, index) {
    if (index >= 0 && index <= this.count) {
        const node = new Node(ele);
        if (index === 0) {
            const current = this.head;
            node.next = current;
            this.head = node;
        } else {
            const prev = this.getVal(index - 1);
            node.next = prev.next;
            prev.next = node;
        }
        this.count++;
        return true;
    }
    return false;
   }
  ···
}

首先需要判斷要插入的位置是否存在，如果不存在則直接返回false，表示不能插入

如果存在，則說明可以插入，那么創(chuàng)建一個節(jié)點。如果需要插入的位置為頭節(jié)點，那么需要將新創(chuàng)建的節(jié)點的next指向頭節(jié)點即可。

如果需要插入的是其他位置，則獲取需要插入位置的前一個節(jié)點prev，將當(dāng)前新插入的節(jié)點的next，指向prev的下一個節(jié)點。然后再將prev的next重新指向需要插入的節(jié)點node即可。

只要是有效的插入元素，都需要對count更新

remove(position)

從鏈表中移除一個元素。

class LinkNodeList {
  constructor() {
    this.head = null;
    this.count = 0;
  }
  ···
  remove(index) {
    if (index >= 0 && index < this.count) {
            let current = this.head;
            // 移除第一項
            if (index === 0) {
                    this.head = current.next;
            } else {
                    const prev = this.getVal(index - 1);
                    current = prev.next;
                    prev.next = current.next;
            }
            this.count--;
            return current.val;
    }

    return undefined;
  }
  ···
}

首先要判斷需要移除的值是否存在，如果不存在則返回undefined

如果移除的是第一個節(jié)點，則直接將頭節(jié)點指向下一個節(jié)點即可。

如果是其他位置的節(jié)點，則首先獲取需要移除位置節(jié)點的前面一個節(jié)點prev,將prev的next,指向下一個，再下一個節(jié)點即可

只要是有效的移除元素，都需要對count更新

toString()

返回表示整個鏈表的字符串。由于列表項使用了Node類，就需要重寫繼承自JavaScript對象默認(rèn)的toString方法，讓其只輸出元素的值。

class LinkNodeList {
  constructor() {
    this.head = null;
    this.count = 0;
  }
  ···
    toString() {
        if (this.head === null) {
            return "";
        }
        let objString = `${this.head.val}`;
        let current = this.head.next;
        for (let i = 1; i < this.size() && current !== null; i++) {
            objString = `${objString}=>${current.val}`;
            current = current.next;
        }
        return objString;
    }
  ···
}

如果頭節(jié)點不存在，則說明是個空鏈表則直接返回空

接下來要做的事情就是將鏈表的每個元素通過“=>”字符串拼接。下面我們看下效果。