Linked Lists

Linked lists are sequence of nodes that are linked together. There are two types of linked lists: Singly and Doubly. Singly linked list is a single node that links to the next and the only reference point to that node. Doubly linked list means that there are two reference points to the next node and the previous.

Traversal

When traversing a linked list you are not allowed to use a forEach or for loop. The next value in a linked list is reliable to guide you through the next linked lists. The efficient way to traverse a linked list is by using a while loop. If you accidentally traverse a node that is null, a nullReferenceError is thrown which causes the program to crash.

Adding a Node

Order of operation is very important when it comes to linked lists. When adding a node with an efficiency O(1) you should replace the current Head of the linked list with the new node.

The required steps to add a node:

Set Current equal to Head. This will guarantee us that we are starting from the very beginning. We can then instantiate the new node that we are adding. The values passed in as arguments into the Add() method will define what the value of the Node will be.

Prerequisites

When constructing your code, a few things to keep in mind. When making a Linked List, you may want to require that at least one node gets passed in upon instantiation. This first node is what your Head and Current will point too. One characteristic of linked lists is that they are linear data structures, which means that there is a sequence and an order to how they are constructed and traversed. In non-linear data structures, items don’t have to be arranged in order, which means that we could traverse the data structure non-sequentially.