patternpythonMinor
Linked list for interviews
Viewed 0 times
listlinkedinterviewsfor
Problem
I'm trying to learn linked lists so I can answer interview questions. Even though I've seen plenty of tutorials to understand how they supposedly work, I don't know if I am doing a good job because I have no one to get feedback from.
```
class Node(object):
def __init__(self, data, next_node = None):
self.data = data
self.next = next_node
def __str__(self):
return str(self.data)
class SinglyLinkedList(object):
def __init__(self):
self.head = None
def prepend(self, data):
'''
Creates a new node and inserts it at the front, making it the head
of the list
'''
self.head = Node(data, next_node=self.head)
def append(self, data):
'''
Creates a new node and inserts it at the very end of the list
'''
new_node = Node(data)
if self.head == None:
self.head = new_node
else:
iter_node = self.head
while iter_node.next:
iter_node = iter_node.next
iter_node.next = new_node
def insert(self, after_node, data):
'''
A new node is created containing the passed data, and then inserted
right after the node called after_node in the list
'''
new_node = Node(data)
new_node.next = after_node.next
after_node.next = new_node
def delete(self, node):
'''
Removes the given node from the list. If the node is at the tail already,
it is set to None. Otherwise it is "de facto" removed by having it mirror the next
node's data, and then link to that mirror's next node.
'''
if node.next == None:
node = None
else:
node.data = node.next.data
node.next = node.next.next
def reverse(self):
'''
Reverses the entire linked list.
'''
if self.head:
prev = None
current = self.head
w
```
class Node(object):
def __init__(self, data, next_node = None):
self.data = data
self.next = next_node
def __str__(self):
return str(self.data)
class SinglyLinkedList(object):
def __init__(self):
self.head = None
def prepend(self, data):
'''
Creates a new node and inserts it at the front, making it the head
of the list
'''
self.head = Node(data, next_node=self.head)
def append(self, data):
'''
Creates a new node and inserts it at the very end of the list
'''
new_node = Node(data)
if self.head == None:
self.head = new_node
else:
iter_node = self.head
while iter_node.next:
iter_node = iter_node.next
iter_node.next = new_node
def insert(self, after_node, data):
'''
A new node is created containing the passed data, and then inserted
right after the node called after_node in the list
'''
new_node = Node(data)
new_node.next = after_node.next
after_node.next = new_node
def delete(self, node):
'''
Removes the given node from the list. If the node is at the tail already,
it is set to None. Otherwise it is "de facto" removed by having it mirror the next
node's data, and then link to that mirror's next node.
'''
if node.next == None:
node = None
else:
node.data = node.next.data
node.next = node.next.next
def reverse(self):
'''
Reverses the entire linked list.
'''
if self.head:
prev = None
current = self.head
w
Solution
-
Bug
-
Interface
Bug
SinglyLinkedList.delete called on the tail node doesn't really delete it: the previous node still holds the reference.-
Interface
SinglyLinkedList.insert and SinglyLinkedList.delete require a handle to a Node object, which is quite hard to obtain. It seems that the only way is to manually iterate the list breaking on a condition. I recommend prepend, append, insert to return a newly created instance. A find method would also be useful.Context
StackExchange Code Review Q#117668, answer score: 2
Revisions (0)
No revisions yet.