Linked List

JavaScript 2

A linked list is a linear data structure where each element (commonly called a node) contains a reference (or link) to the next node in the sequence. Unlike arrays, linked list elements are not stored at contiguous memory locations, allowing for efficient insertions and deletions.

Types of Linked Lists

  1. Singly Linked Lists: Each node has a value and a reference to the next node.
  2. Doubly Linked Lists: Each node has a value, a reference to the next node, and a reference to the previous node.
  3. Circular Linked Lists: Similar to singly or doubly linked lists, but the last node points back to the first node.

Implementing a Singly Linked List

Basic Structure:

A typical node in a singly linked list contains two items:

  • The data (value of the element)
  • A reference to the next node

Example:

javascript 
	class ListNode {
	  constructor(data) {
	    this.data = data;
	    this.next = null;
	  }
	}

Creating a Linked List:

To create a linked list, we start with a head node, which is the first node in the list.

javascript 
	class LinkedList {
	  constructor() {
	    this.head = null;
	  }
	}

Adding Elements:

Here’s how you can add a new node to the end of the list:

javascript 
	class LinkedList {
	  constructor() {
	    this.head = null;
	  }
	
	  add(data) {
	    const newNode = new ListNode(data);
	    if (!this.head) {
	      this.head = newNode;
	    } else {
	      let current = this.head;
	      while (current.next) {
	        current = current.next;
	      }
	      current.next = newNode;
	    }
	  }
	}

NOTE: Adding an element to a linked list involves traversing the list and then adding the new node at the end.

Advantages of Linked Lists

  • Dynamic Size: Unlike arrays, linked lists are dynamic in size and can grow as needed.
  • Efficient Insertions/Deletions: Adding or removing elements doesn’t require shifting elements, as in the case of arrays.

Limitations:

  • No Random Access: You cannot access linked list elements in constant time like arrays.
  • Extra Memory for Pointers: Each element requires extra storage for the reference to the next element.

Practical Example: Using the Linked List

Now let’s use the LinkedList class in a practical scenario. Suppose we are tracking users in an online system, and we want to add them to a list as they join.

javascript 
	// Create a new linked list instance
	let userList = new LinkedList();
	
	// Add some users
	userList.add('Alice');
	userList.add('Bob');
	userList.add('Charlie');
	
	// Display the list of users
	userList.display();

Expected Output:

txt 
	Alice
	Bob
	Charlie

In this example, each time a new user joins, we add them to the userList. When we call userList.display(), it prints out the names of all users in the order they were added.

Further Reading & Resources: