Singly Linked List Fundamentals

1. What is a Linked List?

Unlike an array, which stores elements in a single contiguous block of memory, a linked list is a collection of elements called nodes. Each node is a separate object that contains two key pieces of information:

1. Data: The actual value stored in the node.
2. Next: A reference (or "pointer") to the next node in the sequence.

The first node is called the head, and the last node's next reference points to null, signifying the end of the list.

For a great conceptual overview of why we use linked lists and how they differ from arrays, let's watch the beginning of a detailed tutorial.

2. Building the Foundation in Java

To implement this in Java, we typically use two classes:

1. A private inner Node class to represent each element.
2. The main LinkedList class to manage the overall structure, keeping track of the head, tail, and size.

Let's see how this structure is set up in code.

Here is the basic structure we will build upon. This organization encapsulates the logic and is a standard approach you'll see in interview problems.

public class SinglyLinkedList {

    private Node head;
    private Node tail;
    private int size;

    public SinglyLinkedList() {
        this.size = 0;
    }

    // All our methods (insert, delete, etc.) will go here.

    private class Node {
        private int value;
        private Node next;

        public Node(int value) {
            this.value = value;
        }

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
}

3. Core Operations: Traversal, Insertion, and Deletion

Now, let's implement the essential operations. For each operation, it's crucial to visualize how the pointers (next, head, tail) are manipulated.

Traversal (Displaying the List)

To print the elements, we must traverse the list from head to tail. A common mistake is to move the head pointer itself, which would permanently alter the list. Instead, we use a temporary pointer.

Insertion

We'll cover the three main insertion scenarios: at the beginning, at the end, and at a specific position.

1. Insert at the Beginning (insertFirst): This is an efficient O(1) operation.

   • Create a new node.
   • Set the new node's next to the current head.
   • Update head to point to the new node.
   • Edge Case: If the list was empty, tail must also be set to the new node.

2. Insert at the End (insertLast): Thanks to our tail pointer, this is also an O(1) operation.

   • Create a new node.
   • Set the current tail's next to the new node.
   • Update tail to point to the new node.
   • Edge Case: If the list was empty, this is the same as inserting first.

3. Insert at a Specific Index (insert): This is an O(N) operation as it may require traversal.
   • Traverse to the node just before the target position.
   • Create a new node.
   • Set the new node's next to the previous node's next.
   • Set the previous node's next to the new node.

Let's watch the implementation of these three insertion methods.

Deletion

Like insertion, deletion has three main scenarios. Remember to update the size and handle the edge case where the list becomes empty (updating both head and tail to null).

1. Delete First (deleteFirst): An O(1) operation.

   • Move head to head.next.

2. Delete Last (deleteLast): This is a classic interview question for singly linked lists. It is an O(N) operation.

   • Since we can't go backward from tail, we must traverse from the head to find the second-to-last node.
   • Set the second-to-last node's next to null.
   • Update tail to be the second-to-last node.

3. Delete at a Specific Index (delete): An O(N) operation.

   • Traverse to the node just before the one to be deleted.
   • Update its next pointer to "skip over" the deleted node (i.e., previous.next = previous.next.next).

Let's see the code for these deletion methods.

4. Complexity Analysis

Understanding the time and space complexity is crucial for interviews.

For a concise review of these complexities, the following video is helpful.

Conclusion

Congratulations! You have now implemented a singly linked list from scratch, including its most common operations. This is a significant first step in mastering pointer-based data structures.

Key Takeaways:

• A singly linked list is composed of nodes, each with data and a next pointer.
• The head pointer marks the start, and a null next pointer marks the end.
• Maintaining a tail pointer allows for efficient O(1) insertion at the end.
• Operations that require finding a specific index or the end of the list without a tail pointer (like deleteLast) take O(N) time due to traversal.
• Pointer manipulation requires careful handling of edge cases, such as an empty list or a list with a single node.

Preview of the next lesson:
In this lesson, you saw that some operations, like deleting the last element, were inefficient. In our next lesson, we will address this by exploring the doubly linked list. You will learn to implement a doubly linked list with insertion, deletion, and traversal operations and see how adding a previous pointer can optimize certain actions.