Member-only story
Computer Science Fundamentals With JavaScript Examples
JavaScript is not the language of choice to teach computer science, at least when I was in school. My university algorithms and data structures course was taught in Java. As JavaScript is becoming a more mainstream general purpose language and web developers are expected to have a strong foundation in computer science to be able to write increasingly complex code, it’s worth looking at how those CS 101 data structures and algorithms are implemented in JavaScript. For this article, we are going to look at the Linked List.
What Is A Linked List?
Linked list is like an array but more flexible. Elements in an array are stored contiguously in memory while linked lists are stored as nodes with two fields: current value and a pointer to the next thing in the list. We are going to implement linked list in JavaScript and go over some algorithms with the linked list.
We are only going to focus on singly linked list for this article. Doubly linked lists are also implemented sometimes but having an extra pointer to the predecessor of each node increases the overhead of a linked list as we have to keep twice as many pointers.
Motivation
The main benefit of a linked list is that it is a more memory efficient way of maintaining a dynamic collection of things that could get really large. Because the relationship between the thing and the next thing in the collection is defined by a pointer rather than the proximity in memory, things that are next to each other in the linked list don’t need to be physically stored next to each other in memory. As such, you can use a linked list for solving the following problems:
- Maintain a sorted list that you can keep adding things to without overhead of copying the entire list to a new array.
- Maintain a Last in, first out (LIFO) or a stack. Stacks are used for managing computer processes when your main process get interrupted by calling a subroutine.
Definition
function ListNode(val) {
this.val = val;
this.next = null;
}
