Understanding Linked Lists
There are 3 kinds of Linked Lists, A Single Linked List, a Doubly Linked List, and a Circular Linked List (which can be either single or double). For this post, we’re going to focus on the first, A Single Linked List
Linked Lists are Data Structures that contain nodes, each node has a data field and a next field. The next field points to the next node in the sequence. The first node is called the head, and the last node is called the tail
Some Advantages of them are that they can grow and shrink, allocating and deallocating memory while the program is running. Deletion and Insertion of nodes are easy to implement in a linked list. Disadvantages of Linked Lists are that they do require more memory to store elements in an than an array. They can also be more difficult to traverse, because we cannot access randomly at any node.
Some Applications of a Linked List would be
- Image Viewer: Previous and next images are linked and accessed by using the next and previous buttons
- Web Browser: Previous and next page in a web browser
- Music Player: Playing the next or previous song from a playlist
Let’s set up a basic linked list class. For this, we’ll set up a Node class and a Linked List class.
The Linked List class will also have a constructor which will hold the head of the Linked List. This class also holds various functions that are used to iterate, print, search, add nodes, remove, replace and so much more!
The first function that we see, is the iterate method that takes in a callback. This method will be called in other Linked List methods so that we don’t have to rewrite it every time. Its goal is to traverse the entire LinkedList.
Iterate() sets a count to 0 and a temp to the head of the linked lists. While temp is not null (which would be the case if the Linked List was empty). The result is set to the callback function passing in the temp and count variables. After the callback function is run, if it returns true, we’ll return that value. Otherwise if not true, we’ll increase the count and set the temp to the next node.
A basic example of this would be using the iterate method inside a print method. This will print all the nodes to the console
Above, the iterate method is called and the callback method is the node => console.log(node. value). In this case, the temp value considered the node in the method and will print the value, of all the nodes. Once all the nodes are printed, the very last node’s next value is null, which will break the loop.
There are a lot of different methods that can be implemented using a Linked List. Below is a complete example of what a Linked List class might look like
Here is the tests function I created to make sure that all my methods and classes were working properly
