algoadvance

Design your implementation of the linked list. You can choose to use a singly or doubly linked list.

A node in a singly linked list should have two attributes:

• int val: The value of the node.
• Node next: A reference to the next node in the linked list.

Implement the MyLinkedList class:

• MyLinkedList() Initializes the MyLinkedList object.
• int get(int index) Returns the value of the index-th node in the linked list. If the index is invalid, return -1.
• void addAtHead(int val) Adds 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.
• void addAtTail(int val) Adds a node of value val as the last element of the linked list.
• void addAtIndex(int index, int val) Adds a node of value val before the index-th node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.
• void deleteAtIndex(int index) Deletes the index-th node in the linked list, if the index is valid.

Clarifying Questions

1. Type of Linked List: Should we implement a singly linked list or can we opt for a doubly linked list?
   • We’ll proceed with a singly linked list for simplicity unless otherwise specified.
2. Edge Cases: Should we handle edge cases such as adding/deleting from an empty list?
   • Yes, edge cases should be handled.

Code

class MyLinkedList:
    class ListNode:
        def __init__(self, val=0):
            self.val = val
            self.next = None
    
    def __init__(self):
        self.head = None
        self.size = 0

    def get(self, index):
        if index < 0 or index >= self.size:
            return -1
        current = self.head
        for _ in range(index):
            current = current.next
        return current.val

    def addAtHead(self, val):
        new_node = self.ListNode(val)
        new_node.next = self.head
        self.head = new_node
        self.size += 1

    def addAtTail(self, val):
        new_node = self.ListNode(val)
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
        self.size += 1

    def addAtIndex(self, index, val):
        if index < 0 or index > self.size:
            return
        if index == 0:
            self.addAtHead(val)
        else:
            new_node = self.ListNode(val)
            current = self.head
            for _ in range(index - 1):
                current = current.next
            new_node.next = current.next
            current.next = new_node
            self.size += 1

    def deleteAtIndex(self, index):
        if index < 0 or index >= self.size:
            return
        if index == 0:
            self.head = self.head.next
        else:
            current = self.head
            for _ in range(index - 1):
                current = current.next
            current.next = current.next.next
        self.size -= 1

Strategy

1. Node Class: We define an inner class ListNode to represent each node in the linked list.
2. Initialization: The MyLinkedList class maintains a reference to the head of the list and a size counter.
3. Get Method: Traverse the list until the index is reached, then return the value of that node. Return -1 for invalid indices.
4. Add Methods:
   • addAtHead: New node becomes the new head.
   • addAtTail: Traverse to the end of the list, then append the new node.
   • addAtIndex: Traverse to one node before the specified index, adjust pointers to insert the new node.
5. Delete Method: Traverse to one node before the specified index, adjust pointers to skip the node to be deleted.

Time Complexity

• get(int index): O(n) - Traverses up to index nodes.
• addAtHead(int val): O(1) - Constant time to adjust head pointer.
• addAtTail(int val): O(n) - Traverses entire list to find tail.
• addAtIndex(int index, int val): O(n) - Traverses up to index nodes.
• deleteAtIndex(int index): O(n) - Traverses up to index nodes.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?