Skip to main content

Basics

Design​

707. Design Linked List​

Medium·
2 Approachesclick to switch
How to drive this playground

The playground replays a scripted sequence of MyLinkedList operations and steps through each method on the linked list. Use the operations editor to change the constructor args or the method sequence.

FIG. DESIGN LINKED LIST● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • addAtHead() is O(1) - it only rewires self.sentinel.next.
  • get(), addAtIndex(), and deleteAtIndex() call goToIndex(), which walks node by node from self.sentinel until it reaches index: O(n) in the worst case.
  • addAtTail() walks current_node.next until it falls off the end: O(n) in the worst case.
  • n is the number of nodes currently in the list (self.len).
Space
O(n)
  • Each addAtHead()/addAtTail()/addAtIndex() call allocates one SinglyLLNode, O(1) per call, so the list itself grows to hold up to n nodes.
class SinglyLLNode:
def __init__(self, val: Any, next=None):
self.val = val
self.next = next
 
 
class MyLinkedList:
def __init__(self):
self.sentinel = SinglyLLNode(None, None)
self.len = 0
 
def get(self, index: int) -> int:
node = self.goToIndex(index)
return node.val if node else -1
 
def addAtHead(self, val: int) -> None:
new_node = SinglyLLNode(val)
new_node.next = self.sentinel.next
self.sentinel.next = new_node
self.len += 1
 
def addAtTail(self, val: int) -> None:
new_node = SinglyLLNode(val)
current_node = self.sentinel
while current_node.next:
current_node = current_node.next
current_node.next = new_node
self.len += 1
 
def addAtIndex(self, index: int, val: int) -> None:
prev_node = self.goToIndex(index - 1)
if prev_node:
new_node = SinglyLLNode(val)
new_node.next = prev_node.next
prev_node.next = new_node
self.len += 1
 
def goToIndex(self, index: int) -> Optional[SinglyLLNode]:
current_index = -1
current_node = self.sentinel
while current_node.next and current_index < index:
current_node = current_node.next
current_index += 1
if current_index == index:
return current_node
return None
 
def deleteAtIndex(self, index: int) -> None:
prev_node = self.goToIndex(index - 1)
if prev_node and prev_node.next:
prev_node.next = prev_node.next.next
self.len -= 1

Reusable Code​

Count Linked List Nodes​

Basic·
FIG. COUNT LINKED LIST NODES● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • The while head loop walks every one of the n nodes exactly once.
Space
O(1)
  • Only the scalar length and the head pointer are tracked, independent of n.
def getLen(head):
length = 0
while head:
head = head.next
length += 1
return length