Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

coding interviews > linked lists > Flashcards

linked lists Flashcards

1
Q

initialize node

A

singular:
————————————————————————————-
def __init__(self, data=None):
self.data = data
self.next = None
————————————————————————————-
doubly:
————————————————————————————-
def __init__(self, data=None):
self.data = data
self.next = None
self.prev = None
————————————————————————————-
circular:
————————————————————————————-
def __init__(self, data=None):
self.data = data
self.next = None

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

initialize linked list

A

singular:
————————————————————————————-
def __init__(self):
self.head = None
————————————————————————————-
doubly:
————————————————————————————-
def __init__(self):
self.head = None
self.tail = None
————————————————————————————-
circular:
————————————————————————————-
def __init__(self):
self.head = None
self.tail = None # Maintaining a tail pointer to facilitate easy updates

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

return the number of data elements in the list

A

singular:
————————————————————————————-
def size(self):
current = self.head
count = 0
while current:
count += 1
current = current.next
return count
————————————————————————————-
doubly:
————————————————————————————-
def size(self):
count = 0
current = self.head
while current:
count += 1
current = current.next
return count
————————————————————————————-
circular:
————————————————————————————-
def size(self):
if not self.head:
return 0
count = 1
current = self.head
while current.next != self.head:
count += 1
current = current.next
return count

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

return true if empty

A

singular:
————————————————————————————-
def empty(self):
return self.head is None
————————————————————————————-
doubly:
————————————————————————————-
def empty(self):
return self.head is None
————————————————————————————-
circular:
————————————————————————————-
def empty(self):
return self.head is None

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

return the value of the nth item (starting at 0 for first)

A

singular:
————————————————————————————-
def value_at(self, index):
current = self.head
count = 0
while current:
if count == index:
return current.data
count += 1
current = current.next
raise IndexError(“Index out of range”)
————————————————————————————-
doubly:
————————————————————————————-
def value_at(self, index):
current = self.head
count = 0
while current:
if count == index:
return current.data
count += 1
current = current.next
raise IndexError(“Index out of range”)
————————————————————————————-
circular:
————————————————————————————-
def value_at(self, index):
if self.empty():
raise IndexError(“List is empty”)
current = self.head
for i in range(index):
current = current.next
if current == self.head:
raise IndexError(“Index out of range”)
return current.data

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

add an item to the front of a list

A

singular:
————————————————————————————-
def push_front(self, value):
new_node = Node(value)
new_node.next = self.head
self.head = new_node
————————————————————————————-
doubly:
————————————————————————————-
def push_front(self, value):
new_node = DoubleNode(value)
new_node.next = self.head
if self.head:
self.head.prev = new_node
self.head = new_node
if self.tail is None:
self.tail = new_node
————————————————————————————-
circular:
————————————————————————————-
def push_front(self, value):
new_node = CircularNode(value)
if self.empty():
self.head = self.tail = new_node
new_node.next = new_node # Points to itself, making it circular
else:
new_node.next = self.head
self.head = new_node
self.tail.next = self.head

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

remove the front item and return its value

A

singular:
————————————————————————————-
def pop_front(self):
if self.empty():
raise IndexError(“List is empty”)
value = self.head.data
self.head = self.head.next
return value
————————————————————————————-
doubly:
————————————————————————————-
def pop_front(self):
if self.empty():
raise IndexError(“List is empty”)
value = self.head.data
self.head = self.head.next
if self.head:
self.head.prev = None
else:
self.tail = None
return value
————————————————————————————-
circular:
————————————————————————————-
def pop_front(self):
if self.empty():
raise IndexError(“List is empty”)
value = self.head.data
if self.head == self.tail:
self.head = self.tail = None
else:
self.head = self.head.next
self.tail.next = self.head
return value

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

add an item at the end

A

singular:
————————————————————————————-
def push_back(self, value):
new_node = Node(value)
if self.empty():
self.head = new_node
return
last = self.head
while last.next:
last = last.next
last.next = new_node
————————————————————————————-
doubly:
————————————————————————————-
def push_back(self, value):
new_node = DoubleNode(value)
if self.tail:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
else:
self.head = self.tail = new_node
————————————————————————————-
circular:
————————————————————————————-
def push_back(self, value):
new_node = CircularNode(value)
if self.empty():
self.head = self.tail = new_node
new_node.next = new_node
else:
new_node.next = self.head
self.tail.next = new_node
self.tail = new_node

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

remove end item and return its value

A

singular:
————————————————————————————-
def pop_back(self):
if self.empty():
raise IndexError(“List is empty”)
if self.head.next is None:
value = self.head.data
self.head = None
return value
second_last = self.head
while second_last.next.next:
second_last = second_last.next
value = second_last.next.data
second_last.next = None
return value
————————————————————————————-
doubly:
————————————————————————————-
def pop_back(self):
if self.empty():
raise IndexError(“List is empty”)
value = self.tail.data
self.tail = self.tail.prev
if self.tail:
self.tail.next = None
else:
self.head = None
return value
————————————————————————————-
circular:
————————————————————————————-
def pop_back(self):
if self.empty():
raise IndexError(“List is empty”)
if self.head == self.tail:
value = self.head.data
self.head = self.tail = None
return value
current = self.head
while current.next != self.tail:
current = current.next
value = self.tail.data
self.tail = current
self.tail.next = self.head
return value

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

get the value of the front item

A

singular:
————————————————————————————-
def front(self):
if self.empty():
raise IndexError(“List is empty”)
return self.head.data
————————————————————————————-
doubly:
————————————————————————————-
def front(self):
if self.empty():
raise IndexError(“List is empty”)
return self.head.data
————————————————————————————-
circular:
————————————————————————————-
def front(self):
if self.empty():
raise IndexError(“List is empty”)
return self.head.data

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

get the value of the end item

A

singular:
————————————————————————————-
def back(self):
if self.empty():
raise IndexError(“List is empty”)
last = self.head
while last.next:
last = last.next
return last.data
————————————————————————————-
doubly:
————————————————————————————-
def back(self):
if self.empty():
raise IndexError(“List is empty”)
return self.tail.data
————————————————————————————-
circular:
————————————————————————————-
def back(self):
if self.empty():
raise IndexError(“List is empty”)
return self.tail.data

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

insert value at index, so the current item at that index is pointed to by the new item at the index

A

singular:
————————————————————————————-
def insert(self, index, value):
if index == 0:
self.push_front(value)
return
current = self.head
current_index = 0
while current:
if current_index == index - 1:
new_node = Node(value)
new_node.next = current.next
current.next = new_node
return
current_index += 1
current = current.next
raise IndexError(“Index out of range”)
————————————————————————————-
doubly:
————————————————————————————-
def insert(self, index, value):
if index == 0:
self.push_front(value)
return
current = self.head
for i in range(index):
if current is None:
raise IndexError(“Index out of range”)
current = current.next
if current is None:
self.push_back(value)
else:
new_node = DoubleNode(value)
new_node.prev = current.prev
new_node.next = current
if current.prev:
current.prev.next = new_node
current.prev = new_node
if current == self.head:
self.head = new_node
————————————————————————————-
circular:
————————————————————————————-
def insert(self, index, value):
if index == 0:
self.push_front(value)
return
current = self.head
for i in range(index - 1):
current = current.next
if current == self.head:
raise IndexError(“Index out of range”)
new_node = CircularNode(value)
new_node.next = current.next
current.next = new_node
if new_node.next == self.head:
self.tail = new_node # Update tail if inserted at the end

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

remove node at given index

A

singular:
————————————————————————————-
def erase(self, index):
if index == 0:
return self.pop_front()
current = self.head
current_index = 0
while current:
if current_index == index - 1:
if current.next is None:
raise IndexError(“Index out of range”)
value = current.next.data
current.next = current.next.next
return value
current_index += 1
current = current.next
raise IndexError(“Index out of range”)
————————————————————————————-
doubly:
————————————————————————————-
def erase(self, index):
if index == 0:
return self.pop_front()
current = self.head
for i in range(index):
if current is None:
raise IndexError(“Index out of range”)
current = current.next
if current is None:
raise IndexError(“Index out of range”)
value = current.data
if current.prev:
current.prev.next = current.next
if current.next:
current.next.prev = current.prev
if current == self.head:
self.head = current.next
if current == self.tail:
self.tail = current.prev
return value
————————————————————————————-
circular:
————————————————————————————-
def erase(self, index):
if self.empty():
raise IndexError(“List is empty”)
if index == 0:
return self.pop_front()
current = self.head
for i in range(index - 1):
current = current.next
if current.next == self.head:
raise IndexError(“Index out of range”)
if current.next == self.tail:
self.tail = current
value = current.next.data
current.next = current.next.next
return value

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

return the value of the node at the nth position from the end of a list

A

singular:
————————————————————————————-
def value_n_from_end(self, n):
size = self.size()
current = self.head
current_index = 0
target_index = size - n - 1
while current:
if current_index == target_index:
return current.data
current_index += 1
current = current.next
raise IndexError(“Index out of range”)
————————————————————————————-
doubly:
————————————————————————————-
def value_n_from_end(self, n):
current = self.tail
for i in range(n):
if current is None:
raise IndexError(“Index out of range”)
current = current.prev
if current is None:
raise IndexError(“Index out of range”)
return current.data
————————————————————————————-
circular:
————————————————————————————-
def value_n_from_end(self, n):
size = self.size()
target_index = size - n
if target_index < 0:
raise IndexError(“Index out of range”)
current = self.head
for i in range(target_index):
current = current.next
return current.data

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

reverse a list

A

singular:
————————————————————————————-
def reverse(self):
previous = None
current = self.head
while current:
next_node = current.next
current.next = previous
previous = current
current = next_node
self.head = previous
————————————————————————————-
doubly:
————————————————————————————-
def reverse(self):
current = self.head
self.head, self.tail = self.tail, self.head
while current:
current.prev, current.next = current.next, current.prev
current = current.prev
————————————————————————————-
circular:
————————————————————————————-
def reverse(self):
if self.empty() or self.head == self.tail:
return
prev = self.tail
current = self.head
next_node = None
while current != self.tail:
next_node = current.next
current.next = prev
prev = current
current = next_node
current.next = prev
self.head, self.tail = self.tail, self.head

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

remove the first item in the list with a value

A

singular:
————————————————————————————-
def remove_value(self, value):
current = self.head
if current and current.data == value:
self.head = current.next
return
while current and current.next:
if current.next.data == value:
current.next = current.next.next
return
current = current.next
raise ValueError(“Value not found”)
————————————————————————————-
doubly:
————————————————————————————-
def remove_value(self, value):
current = self.head
while current:
if current.data == value:
if current.prev:
current.prev.next = current.next
if current.next:
current.next.prev = current.prev
if current == self.head:
self.head = current.next
if current == self.tail:
self.tail = current.prev
return
current = current.next
raise ValueError(“Value not found”)
————————————————————————————-
circular:
————————————————————————————-
def remove_value(self, value):
if self.empty():
raise ValueError(“List is empty”)
current = self.head
if current.data == value:
self.pop_front()
return
prev = None
while current != self.tail:
prev = current
current = current.next
if current.data == value:
prev.next = current.next
if current == self.tail:
self.tail = prev
return
if self.tail.data == value: # Check tail separately
self.pop_back()
return
raise ValueError(“Value not found”)

coding interviews (4 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions