什么是鏈表

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

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

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

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

JS實(shí)現(xiàn)一個(gè)鏈表

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

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

Node類(lèi)

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

創(chuàng)建鏈表類(lèi)

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

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

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

size

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

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

isEmpty

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

直接判斷size 是否為0即可

push

向鏈表尾部添加一個(gè)新元素。

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++;
  }
  ···
}

如果想鏈表的尾部添加一個(gè)元素，那么首先需要通過(guò)上面實(shí)現(xiàn)的Node類(lèi)來(lái)創(chuàng)建一個(gè)節(jié)點(diǎn)。如果當(dāng)前的head還不存在，則說(shuō)明當(dāng)前的鏈表還是一個(gè)空，所以直接將head節(jié)點(diǎn)賦值即可。否則就找到鏈表的最后一個(gè)節(jié)點(diǎn)，將它的next指向新push的節(jié)點(diǎn)即可。并且將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.

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

insert(element, position)

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

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，表示不能插入

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

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

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

remove(position)

從鏈表中移除一個(gè)元素。

class LinkNodeList {
  constructor() {
    this.head = null;
    this.count = 0;
  }
  ···
  remove(index) {
    if (index >= 0 && index < this.count) {
            let current = this.head;
            // 移除第一項(xiàng)
            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

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

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

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

toString()

返回表示整個(gè)鏈表的字符串。由于列表項(xiàng)使用了Node類(lèi)，就需要重寫(xiě)繼承自JavaScript對(duì)象默認(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é)點(diǎn)不存在，則說(shuō)明是個(gè)空鏈表則直接返回空

接下來(lái)要做的事情就是將鏈表的每個(gè)元素通過(guò)“=>”字符串拼接。下面我們看下效果。

以上就是JS實(shí)現(xiàn)鏈表數(shù)據(jù)結(jié)構(gòu)的代碼詳解的詳細(xì)內(nèi)容，更多關(guān)于JS實(shí)現(xiàn)鏈表數(shù)據(jù)結(jié)構(gòu)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論