8
\$\begingroup\$

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 = ' <-> ' if doubly else ' -> '
        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) > 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:

  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?

\$\endgroup\$
  • 1
    \$\begingroup\$ 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/… \$\endgroup\$ – dfhwze Jul 27 at 21:13
  • \$\begingroup\$ thanks, sry about that :) \$\endgroup\$ – Matan Cohen Jul 27 at 22:54
1
\$\begingroup\$

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

Advise

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:
    link_symbol = ' -> '

    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

class DoubleLinkedList(LinkedList):
    link_symbol = ' <-> '

    @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

    def head(self):
        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.

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Matan Cohen Jul 20 at 16:50
  • 1
    \$\begingroup\$ @MatanCohen good catch, it was supposed to be a class, so I have corrected that. \$\endgroup\$ – Ninetails Jul 20 at 17:03
  • \$\begingroup\$ 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 \$\endgroup\$ – Matan Cohen Jul 25 at 17:19
  • \$\begingroup\$ 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. \$\endgroup\$ – Ninetails Jul 26 at 20:31
  • 1
    \$\begingroup\$ I had to roll back your changes. Your edit invalidated both answers. Please ask a new question if you wish us to review your updated code. thanks \$\endgroup\$ – dfhwze Jul 27 at 21:18
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thank you so much!! noted \$\endgroup\$ – Matan Cohen Jul 20 at 16:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.