Linked Lists

This is a brief overview of what a linked list is.

What is a linked list?

A linked list is a data structure. It consists of nodes, where each node has a data field (a value) and a pointer to the next node (or in addition to the previous node). This is unlike an array (which is what comes to mind when thinking of a list) which holds its elements in contiguous memory locations.

A linked list has a head (first node), a tail (last node), and a length. In order to get to anywhere in the linked list, you need to start at the head and go to the next one until you come to the node you were looking for. The last node (the tail) doesn’t have a pointer to another node but is null.

Linked List vs Array

Linked list doesn’t have indexes. This is an advantage for insertion or deletion. Where in an array, if you would like to make an insert at the front of an array it would have to shift the entire array one index over; a linked list would just be making a new head with another pointer. But a disadvantage is that there is no random access. You can’t access the middle of a list. Compare that to an array where you can just ask for the index of what you are looking for.

Traversing Linked Lists

To traverse a linked list all we need to do is follow the pointers until the end. We will use a while loop to iterate through one.

function traverse(linkedList){
  // declare a variable that we will use to keep track of the current head
  let head = linkedList
  // An array to hold all the values of the linked list
  let data = []
  // while loop that keeps going until the current head is null which mean we reach the end
  while (head !== null) {
    data.push(head.val)
    // change head to the next node
    head = head.next
  }
  // return the array with the values
  return data
}

That’s it! I hope this helps you understand this important data structure. Happy coding!