JavaScript data structure: list of links

Linked lists are one of the most important data structures you can learn.

In the linked list, each item contains a reference to the item following it.

We can start from the beginning of the listhead, And then iterate through all the items in the list until it reaches the end (tail).

In contrast to arrays, items are not adjacent to each other in actual memory (using low-level programming languages), or there is no index that can be used to randomly access array items.

We cannot refer to the item in the middle of the list from the beginning of the list, because we don't know how to refer to it.

JavaScript does not have an implementation of linked lists, so we will create one now.

First, we createItemThe classes that each item in the list will contain:

class Item {
  next = null
  value = null
  constructor(value) {
    this.value = value
  }
}

We have a pointer to the next item and value in the list.

Then we definedLinkedListClasses that will host 2 private values:headwithtail.

We define aappend()Method of adding items to the list. If this is the first item we add, it is both the beginning and the end of the list. Otherwise, we will create the project and assign it tonextThe attributes of the last item:

class LinkedList {
  #head = null
  #tail = null
  append = (value) => {
    const item = new Item(value)
    if (!this.#head) {
      this.#head = item
      this.#tail = item
      return
    }
    this.#tail.next = item
    this.#tail = item
  }
  size = () => {
    let count = 1
    let item = this.#head
    if (!item) return 0
    while ((item = item.next)) {
      count++
    }
    return count
  }
}

This is how we use it:

const list = new LinkedList()
list.append(1)
list.append(2)
list.append(3)

We can add asize()How to return the size of the list:

class LinkedList {
  //...
  size = () => {
    let count = 1
    let item = this.#head
    if (!item) return 0
    while ((item = item.next)) {
      count++
    }
    return count
  }
}
const list = new LinkedList()
list.size() //0
list.append(1)
list.size() //1
list.append(2)
list.append(3)
list.size() //3

How can we find an item in the list by value? Let's implement a method to do this:

class LinkedList {
  //...
  find = (value) => {
    let count = 1
    let item = this.#head
    if (!item) return null
    while ((item = item.next)) {
      if (item.value === value) {
        return item
      }
    }
    return null
  }
}

const list = new LinkedList() list.append(1) list.append(2) list.append(3) const item = list.find(2) //item.value === 2

What if we want to insert an item in the link list? We already haveappend()Insert the item at the end of the list. Let's implement a way to insert an item at a specific location:

class LinkedList {
  //...
  insert = (index, value) => {
    //check for out-of-bounds values
    if (index < 0 || index > this.size()) return
<span style="color:#66d9ef">const</span> <span style="color:#a6e22e">node</span> <span style="color:#f92672">=</span> <span style="color:#66d9ef">new</span> <span style="color:#a6e22e">Item</span>(<span style="color:#a6e22e">value</span>)
<span style="color:#66d9ef">let</span> <span style="color:#a6e22e">current</span> <span style="color:#f92672">=</span> <span style="color:#66d9ef">this</span>.<span style="color:#960050;background-color:#1e0010">#</span><span style="color:#a6e22e">head</span>
<span style="color:#66d9ef">let</span> <span style="color:#a6e22e">previous</span>

<span style="color:#66d9ef">if</span> (<span style="color:#a6e22e">index</span> <span style="color:#f92672">===</span> <span style="color:#ae81ff">0</span>) {
  <span style="color:#75715e">//first position

node.next = current this.#head = node } else { let i = 0 while (i++ < index) { previous = current current = current.next } node.next = current previous.next = node } } }

const list = new LinkedList() list.append(1) list.append(2) list.append(3) list.insert(2, ‘a’) list.size() //4

Another type of linked list is a double-linked list, where each item also contains a link to the previous element.

Download mine for freeJavaScript beginner's manual


More js tutorials: