# Implementing Linked lists in Python from scratch

After finishing my ds and algorithms course I wanted to implement what I've learned through the semester so here is my try for Linked lists, both regular (one way) and double one (two way).

code:

from node import ListNode

_length = 0

''' double is boolean '''
def __init__(self, x, doubly=False):
if x is not None:
self._length += 1
else:
assert False, 'User entered a None value'

''' representing the list '''
def __str__(self, doubly=False):
st = ''
arrow = ' <-> ' if doubly else ' -> '
while p is not None:
st += str(p.key)
p = p.next
if p is not None:
st += arrow
return st

''' insert to the end of the list '''
def insert(self, x, doubly=False):
self.__init__(x)
return
new_node = ListNode(x, doubly)
self.tail.next = new_node
if doubly:
new_node.prev = self.tail
self.tail = new_node
self._length += 1

''' insert to the head of the list '''
new_node = ListNode(x, doubly)
if doubly:
self._length += 1

''' delete from list and fix pointers '''
def delete(self, x, doubly=False):
''' deleting first instance of x '''
# if list is empty
raise Exception('List is empty')
# else..
# if head is x, delete and fix
if p.key == x:
if len(self) > 1:
if doubly:
p.next.prev = None
self._length -= 1
else:
self._length -= 1
return
del p
return
# regular delete from list
while p.next is not None and p.next.key != x:
p = p.next
if p.key != x:
return None
tmp = p.next  # grab Node contains x
if self.tail is tmp:
self.tail = p
p.next = p.next.next
if doubly:
p.next.next.prev = p
del tmp
self._length -= 1

''' search (linear time O(n)) in list '''
def search(self, x):
return None
if p.key == x:
return p
while p.key != x and p.next is not None:
p = p.next
return p if p.key == x else None

_length = 0

''' Init double linked list '''
def __init__(self, x):
super().__init__(x, True)

''' string with doublt linkedlist '''
def __str__(self):
return super().__str__(True)

def __len__(self):
return self._length

def insert(self, x):
super().insert(x, True)

def delete(self, x):
super().delete(x, True)

def search(self, x):
return super().search(x)


the Node class:

class ListNode():
def __init__(self, x, double=False):
self.key = x
self.next = None
if double:
self.prev = None

def __str__(self):
try:
return str(self.key)
except AttributeError:
return 'No key for this Node'


thanks in advance for you code review!

Things I want to check:

1. is the code is understandable?

2. is it well organized?

3. is the implementation using abstract class is good or there are conventions I missed/etc ?

4. any other suggestions?

• After answers were made, the original code cannot be updated. It is advised to ask a follow-up question instead, if you want a review of your updated code: meta.stackexchange.com/questions/286803/… – dfhwze Jul 27 '19 at 21:13

## Problems

The use of _length in your classes is problematic, because that value is shared between all instances of the same class, which means it will refere to the wrong value when you have multiple non-empty lists of the same type. One of the big problems with linked lists in general is the loss of this length information if you do not package the list (and thereby loss the value of having a linked list).

It is generally advised to mainly focus on the nodes when creating linked lists, as the main power of linked list comes from doing operations locally (around some node that you know of), instead of from a common interface (iterating through such a list would be expensive if we need to walk from the beginning each time we want to reference the next position).

There is also a point to be made about trying to implement some of pythons hooks for lists, which can make the rest of the implementation much easier to do.

## Implementation

Here is how I would go about this, note that prepending is generally done by just calling head = LinkedList(value, head):

class LinkedList:

def __init__(self, value, next=None):
self.value = value
self.next = next

def as_generator(self, end=None):
node = self
yield node
while node.next is not end and node.next is not None:
node = node.next
yield node

def __iter__(self):
return map(lambda node: node.value, self.as_generator())

def __str__(self):
return self.link_symbol.join(value for value in self)

def delete_next(self):
if self.next is not None:
self.next = self.next.next

def forward(self, steps):
for node in self.as_generator():
if steps == 0:
return node
steps -= 1

def __getitem__(self, steps):
return self.forward(steps).value

def __reverse__(self):
return self.__class__.from_iter(self, reversed=True)

@classmethod
def from_iter(cls, iter, start=None, reversed=True):
result = start
for value in iter:
cls(value, result)
if not reversed:
result.reversed()
return result

def tail(self):
for node in self.as_generator():
pass
return node

def __len__(self):
return sum(1 for __ in self)

def append(self, value):
self.tail().next = self.__class__(value)

def find(self, value):
for node in self.as_generator():
if node.value = value:
return node

@property
def next(self):
return self.__next

@next.setter
def next(self, node):
if node is not None:
node.prev = self
self.__next = node

def __init__(self, value, next=None, prev=None, cyclic=True):
super().__init__(value, next)
self.prev = prev
if cyclic and self.next is None and self.prev is None:
self.next, prev = (self, self)

def as_generator(self, end=None)
if end is None:
end = self
super().as_generator(end=end)

# extra stuff we can now do
def backwards_generator(self, end=None):
node = self
yield node
while node.prev is not end and node.prev is not None:
node = node.prev
yield node

def backwards(self, steps):
if steps < 0:
return self.forward(-steps)
for node in self.backwards_generator():
if steps == 0:
return node
steps -= 1

for node in self.backwards_generator():
pass
return node

def forward(self, steps)
if steps < 0:
return self.backwards(-steps)
return super().forward(steps)


Note how much easier it was to make DoubleLinkedList when most of the methods is expressed in terms of central functions instead of having each implementing their own specific version of a walk through the list.

• Thank you so much!! I got so much to learn, i'll go over it as soon as possible in order to understand it better :) BTW I think you made LinkedList as a method instead of a Class, am I right? – Matan Cohen Jul 20 '19 at 16:50
• @MatanCohen good catch, it was supposed to be a class, so I have corrected that. – Ninetails Jul 20 '19 at 17:03
• while deeping into the code I saw that in order to get tail we need to iterate over the entire list. it takes O(n) time. why not define an attribute and update it every append? :) also, the length takes O(n) too, why can't we maintain the length as an attribute? Also, while trying to append/print DoubleLinkedList I get TypeError: 'NoneType' object is not iterable – Matan Cohen Jul 25 '19 at 17:19
• The O(n) cost of tail and length is indeed not a mistake, and it is a side effect of node based implementation. It is generally advisable to keep such information separately if you are working with the list in such a context (keep the tail around if you do a lot of appending), and you can add a wrapper around it if you tend to do a lot of those opperations,. You do lose out on a lot of the power of linked lists if you do so though, since you would need a restricted interface. Remember that a node can be part of a whole inversed tree of linked list, and the priced local operations breaks. – Ninetails Jul 26 '19 at 20:31

### Review

You should take advantage of the bi-directional nature of a doubly linked list. It's a pitty to let it use navigation of a normal linked list just for the sake of enabling inheritance. And why should a normal linked list be able to branch between normal and doubly mode? This is a code smell.

A practical way to create a doubly linked list, is to create a circular list. You only need to store the head. tail would be head.prev. This also works with a single node head = head.prev = head.next. The advantage is that less if statements are required to perform insert / delete operations. Walking the nodes starts at head and stops until we encounter head again. We could walk both directions if we wish to.

You can initialise a single node:

self.head = ListNode(x, doubly)


The delete would be significantly simplified:

After walking the nodes until you get the proper node p given x, you can call

if p.next == p:
else:
p.next.prev = p.prev
p.prev.next = p.next

I also don't get why you store p = self.head in insert. It's an unused variable.