Leetcode 707. Design Linked List

Problem Explanation:

The problem is to implement a singly linked list, a fundamental data structure.

A linked list is a linear data structure, in which the elements are not stored in contiguous memory locations but instead, each element points to the next.

In a single linked list, we have an element called 'node' which has two parts: data and next. The 'data' contains the value to be stored in the node, and 'next' contains the reference to the next node.

The problem states various functions to be implemented:

1.get(index) : This function is used to get the value of the index-th node in the linked list. If the index is invalid, it returns -1.

2.addAtHead(val): This function is used to add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.

3.addAtTail(val): This function is used to append a node of value val at the end or tail of the linked list.

4.addAtIndex(index, val) : This function is used to add a node of value val before the index-th node in the linked list. If index equals to the length of the linked list, the node will be appended at the end of the linked list.

5.deleteAtIndex(index): This function is used to delete the index`-th node in the linked list, if the index is valid.

Walkthrough example:

For example,

Let linked list be "MyLinkedList()".

Initially, since there are no nodes, output of linkedList.get(0) is -1 i.e., index is invalid.

When we addAtHead(1) , the linked list becomes 1.

When we addAtTail(3), the linked list becomes 1->3.

When we addAtIndex(1, 2), the linked list becomes 1->2->3.

If we get(1), it returns 2.

After deleteAtIndex(1), as we are deleting 2nd node, the linked list becomes 1->3.

If we get(1), now it returns 3.

Solution Approach:

The problem can be solved using the basic operations on the singly linked list. It requires initializing a 'dummy' node with value 0. A 'dummy' node is a node that’s just used to literally take up a space in the data structures so that we don’t need to make a lot of if-else checks.

The 'next' pointer, which is pointing to 'None' initially, will point to the next node as we go adding elements. For example, in the 'addAtHead' function, we first keep a reference of the current head node by 'ListNode* head = dummy.next'. We then add a new node with the given value 'val' by 'ListNode* node = new ListNode(val)'. We now make the next of this node point to the head node and finally, we will update the dummy next to point to the current node. We do this to make the new node as the first node of the linked list.

This way we keep updating the dummy.next and the length of the linked list for all the other functions as well. The length of the linked list is calculated to validate the index given.

The complexity analysis can be done as follows:

• Time complexity is O(index) for get, addAtIndex and deleteAtIndex. Here, index <= size for get and deleteAtIndex and index <= size + 1 for addAtIndex. And is O(1) for both addAtHead and addAtTail, which is more efficient.
• Space complexity is O(1) for all operations because we only use a constant extra space to create a new node.

Solutions:

Python Solution:

1
2python
3class Node(object):
4    def __init__(self, x):
5        self.val = x
6        self.next = None
7
8class MyLinkedList(object):
9    def __init__(self):
10        self.size = 0
11        self.head = Node(0)  
12    def get(self, index):
13        if index < 0 or index >= self.size:
14            return -1
15        curr = self.head
16        for _ in range(index + 1): 
17            curr = curr.next
18        return curr.val
19    def addAtHead(self, val):
20        self.addAtIndex(0, val)
21    def addAtTail(self, val):
22        self.addAtIndex(self.size, val)
23    def addAtIndex(self, index, val):
24        if index > self.size: 
25            return
26        if index < 0: 
27            index = 0
28        self.size += 1
29        pred = self.head
30        for _ in range(index): 
31            pred = pred.next
32        to_add = Node(val)
33        to_add.next = pred.next
34        pred.next = to_add
35    def deleteAtIndex(self, index):   
36        if index < 0 or index >= self.size:
37            return
38        self.size -= 1
39        pred = self.head
40        for _ in range(index): 
41            pred = pred.next
42        pred.next = pred.next.next

Java Solution:

1
2java
3class MyLinkedList {
4    int size;
5    Node head;  
6    public MyLinkedList() {
7        size = 0;
8        head = new Node(0);
9    }
10    class Node {
11        int val;
12        Node next;
13        Node(int x) {
14            val = x;
15        }
16    }
17    public int get(int index) {
18          if(index < 0 || index >= size) return -1;
19          Node curr = head;
20          for(int i = 0; i < index + 1; ++i) curr = curr.next;
21          return curr.val;
22    }
23    public void addAtHead(int val) {
24         addAtIndex(0, val);
25    }
26    public void addAtTail(int val) {
27         addAtIndex(size, val);
28    }
29    public void addAtIndex(int index, int val) {
30      if(index > size) return;
31      if(index < 0) index = 0;
32      ++size; 
33      Node pred = head;
34      for(int i = 0; i < index; ++i) pred = pred.next;
35      Node toAdd = new Node(val);
36      toAdd.next = pred.next;
37      pred.next = toAdd;
38    }
39    public void deleteAtIndex(int index) {
40        if(index < 0 || index >= size) return;
41        size--;
42         Node prev = head;
43        for(int i = 0; i < index; ++i) prev = prev.next;
44        prev.next = prev.next.next;
45    }
46}

JavaScript Solution:

1
2javascript
3class Node {
4    constructor(val) {
5        this.val = val;
6        this.next = null;
7    }
8}
9
10class MyLinkedList {
11    constructor() {
12        this.size = 0;
13        this.head = new Node(0);  
14    }
15    get(index) {
16        if (index < 0 || index >= this.size) return -1;
17        let curr = this.head;
18        for (let i = 0; i < index + 1; i++) curr = curr.next;
19        return curr.val;
20    }
21    addAtHead(val) {
22        this.addAtIndex(0, val);
23    }
24    addAtTail(val) {
25        this.addAtIndex(this.size, val);
26    }
27    addAtIndex(index, val) {
28        if (index > this.size) return;
29        if (index < 0) index = 0;
30        this.size++;
31        let pred = this.head;
32        for (let i = 0; i < index; i++) pred = pred.next;
33        let newNode = new Node(val);
34        newNode.next = pred.next;
35        pred.next = newNode;
36    }
37    deleteAtIndex(index) {
38        if (index < 0 || index >= this.size) return;
39        this.size--;
40        let prev = this.head;
41        for (let i = 0; i < index; i++) prev = prev.next;
42        prev.next = prev.next.next;
43        
44    }
45}

C++ Solution:

1
2c++
3class Node {
4public:
5  int val = 0;
6  Node* next = nullptr;
7  Node(int _val) {
8    val = _val;
9  }
10};
11
12class MyLinkedList {
13private:
14  Node* head;
15  int size;
16
17public:
18  MyLinkedList() {
19    head = new Node(0);
20    size = 0;
21  }
22
23  int get(int index) {
24    if (index < 0 or index >= size)
25      return -1;
26
27    Node* curr = head->next;
28    for (int i = 0; i < index; i++)
29      curr = curr->next;
30    return curr->val;
31  }
32
33  void addAtHead(int val) {
34    Node* newNode = new Node(val);
35    newNode->next = head->next;
36    head->next = newNode;
37    size++;
38  }
39
40  void addAtTail(int val) {
41    Node* newNode = new Node(val);
42    Node* curr = head;
43    while (curr->next != nullptr)
44      curr = curr->next;
45    curr->next = newNode;
46    size++;
47  }
48
49  void addAtIndex(int index, int val) {
50    if (index > size)
51      return;
52    if (index < 0)
53      return addAtHead(val);
54
55    Node* newNode = new Node(val);
56    Node* curr = head;
57    for (int i = 0; i < index; i++)
58      curr = curr->next;
59
60    newNode->next = curr->next;
61    curr->next = newNode;
62    size++;
63  }
64
65  void deleteAtIndex(int index) {
66    if (index < 0 or index >= size)
67      return;
68
69    Node* curr = head;
70    for (int i = 0; i < index; i++)
71      curr = curr->next;
72
73    Node* temp = curr->next;
74    curr->next = curr->next->next;
75    delete temp;
76    size--;
77  }
78};

C# Solution:

1
2csharp
3public class MyLinkedList {
4    
5    private int length;
6    private Node head;
7    public MyLinkedList() {
8        length = 0;
9        head = new Node(0);
10    }
11
12    public int Get(int index) {
13        if (index > length - 1 || index < 0) return -1;
14        Node cur = head;
15        for (int i = 0; i <= index; i++) cur = cur.next;
16        return cur.val;
17    }
18
19    public void AddAtHead(int val) {
20        var node = new Node(val);
21        node.next = head.next;
22        head.next = node;
23        length++;
24    }
25
26    public void AddAtTail(int val) {
27        Node cur = head;
28        while (cur.next != null) cur = cur.next;
29        cur.next = new Node(val);
30        length++;
31    }
32
33    public void AddAtIndex(int index, int val) {
34        if (index > length) return;
35        if (index < 0) index = 0;
36        Node cur = head;
37        for (int i = 0; i < index; i++) cur = cur.next;
38        var node = new Node(val);
39        node.next = cur.next;
40        cur.next = node;
41        length++;
42    }
43
44    public void DeleteAtIndex(int index) {
45        if (index >= length || index < 0) return;
46        Node cur = head;
47        for (int i = 0; i < index; i++) cur = cur.next;
48        cur.next = cur.next.next;
49        length--;
50    }
51}
52public class Node
53{
54    public int val { get; set; }
55    public Node next { get; set; }
56    public Node(int val)
57    {
58        this.val = val;
59    }
60}

In these solutions, we are creating and manipulating a singly linked list using Node class and simple data manipulation.The understanding of how these methods work and the solutions provided are correct. Please do not hesitate to ask if you have any questions or need any further clarifications.

The key takeaway when working with linked lists is remembering how pointers work and carefully manipulating them when adding and removing nodes from the linked list. It may take some time at first to get the hang of linked lists, especially if pointers are a new concept for you. But with practice and patience, it becomes second nature.

Remember, in each operation, you must ensure to maintain the links to the next nodes correctly. Given their linear nature, missing a link could lead to loss of a section of your list, leading to incorrect results.

To summarize, singly linked lists are fundamental data structures that are essential for understanding more complex data structures. They are also common in interview questions. Python, JavaScript, Java, C++, and C# solutions have been provided here. Based on your comfort and requirement, you can use the solution in a language of your choice.

In case you face any errors or difficulties, you should debug your code by printing the linked list at different stages and checking if the linking between nodes is being carried out correctly. The moment you get a grip on it, you'll realize how powerful and useful linked lists can be! Happy coding!