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


class LinkedList():
    _length = 0

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

    ''' representing the list '''
    def __str__(self, doubly=False):
        st = ''
        arrow = ' &lt;-&gt; ' if doubly else ' -&gt; '
        p = self.head
        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):
        if self.head is None:
            self.__init__(x)
            return
        p = self.head
        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 '''
    def insert_to_head(self, x, doubly=False):
        new_node = ListNode(x, doubly)
        new_node.next = self.head
        if doubly:
            self.head.prev = new_node
        self.head = new_node
        self._length += 1

    ''' delete from list and fix pointers '''
    def delete(self, x, doubly=False):
        ''' deleting first instance of x '''
        # if list is empty
        if self.head is None:
            raise Exception('List is empty')
        # else..
        p = self.head
        # if head is x, delete and fix
        if p.key == x:
            if len(self) &gt; 1:
                if doubly:
                    p.next.prev = None
                self.head = p.next
                self._length -= 1
            else:
                self.head, self.tail = None, None
                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):
        if self.head is None:
            return None
        p = self.head
        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


class DoublyLinkedList(LinkedList):

    _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 insert_to_head(self, x):
        super().insert_to_head(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:


is the code is understandable?
is it well organized?
is the implementation using abstract class is good or there are conventions I missed/etc ?
any other suggestions?
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)
self.head.prev = self.head
self.head.next = self.head


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:
    self.head = None
else:
    p.next.prev = p.prev
    p.prev.next = p.next
    if self.head == p:
        self.head = p.next
del p
self._length -= 1


I don't see a value in using inheritance for these lists.



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