HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

Linked list for interviews

Submitted by: @import:stackexchange-codereview··
0
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

Solution

-
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.