Introduction to Linked Lists

In this lesson, we will explore the concept of linked lists, understand the role of nodes, examine the structure of linked lists, and discuss their advantages over arrays.

Arrays vs Linked Lists

In programming, arrays and linked lists are different ways to organize and store data. Let's start with arrays. Imagine an array as a row of boxes, where each box can hold an item of data. When we create an array, we need to allocate a certain amount of memory to hold all the boxes. For example, if we have an array to store eight letters, we allocate memory for eight boxes. The important thing to note is that these boxes need to be placed next to each other in a contiguous block of memory.

On the other hand, linked lists are more flexible. Instead of boxes in a row, think of linked lists as a series of individual nodes, each containing some data and a reference to the next node. Each node is like a little container with its own data and a pointer to the next container. Unlike arrays, these nodes don't need to be located together in a single block of memory. They can be scattered throughout the computer's memory.

Now, let's discuss the dynamic nature of arrays and linked lists. Arrays are static data structures because they require all the memory they need to be allocated upfront. If you want to add more items to an already full array, you need to create a new, larger array and copy all the existing items into it. This can be time-consuming and memory-intensive.

Linked lists, on the other hand, are dynamic data structures. They can grow or shrink in size as needed. Adding or removing items in a linked list is easier because you don't need to worry about finding contiguous memory blocks or copying data. You can simply rearrange the pointers in the nodes to link them correctly.

---

The Structure of a Linked List

Let's dive into the structure of a linked list. A linked list is composed of nodes. The first node in the list is called the head, which serves as the starting point to access the rest of the list. Each node contains two things: the actual data it holds and a reference (or pointer) to the next node in the list. Think of it as a chain of nodes, where each node holds some data and points to the next node in line. Almost every linked list requires a head, which is the primary access point to the list and all its elements. Without a head, determining the starting point becomes impossible. The final node in the list has its next pointer pointing to null, indicating the end of the list rather than another node.

---

Types of Linked Lists

Now, let's consider different types of linked lists.

• A singly linked list is a data structure in which each node contains data and a reference to the next node in the sequence. This allows traversal only in one direction, from the head (first node) to the tail (last node), with the last node pointing to null.

In contrast, a doubly linked list features nodes that contain data, a reference to the next node, and a reference to the previous node. This enables traversal in both directions, from head to tail and tail to head, with the first node's previous pointer and the last node's next pointer pointing to null.

Finally, a circular linked list is similar to a singly linked list, but the last node points back to the first node, creating a continuous loop without any null references. This means traversal can start at any node and circularly proceed through the entire list.

---

Implementing a Linked List

In this course, we will focus exclusively on singly linked lists, which are more commonly encountered in job interviews and coding challenges.

Lastly, we want to mention that there are several ways to implement a linked list, and for this course, we will focus on the Node-as-a-class approach.

What does "Node-as-a-class" mean? In this approach, each node of the linked list is represented as an instance of a Node class. The Node class consists of two main components: the data we want to store in the node and a reference to the next node in the list.

By utilizing classes, we can encapsulate the properties and behavior of each node into a single entity, making it a clean and organized way to conceptualize linked lists.

To implement a linked list using the Node-as-a-class approach, we can define a Node class in JavaScript. Here's an example:

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

In this implementation, a linked list is represented by its "head" node, the first node in the list. To traverse the linked list, we start from the head node and follow the subsequent references until we reach the desired node or the end of the list.

It's worth noting that there are other implementations where a class called LinkedList holds Node objects. However, in the Node-as-a-class approach, there is no way to encapsulate the entire linked list. Instead, we can only have a reference to its "head" node and traverse from there.

This way of representing linked lists is the most common in job interviews. Typically, you will be given the "head" node as input, which will serve as your access point to the rest of the linked list.

In the next assignment, we will explore the time efficiency of different operations on linked lists and understand how they differ from arrays.