5
\$\begingroup\$

Note: I do know that Python libraries provide linked a linked list. This implementation has been done to practice.

I have implemented double Linked List without Sentinels and the code seems to work just fine. There is a Node class that is used within the DoubleLinkedList class. There is also a test.py to show that the code works

Request:
Feel free to criticize and give pointers

Targeted Time:
Search: \$O(n)\$ at worse
Insert and delete: \$O(1)\$

Methods:

  1. list_add
  2. list_delete
  3. list_search
  4. get_top

Both class:

class Node:
    def __init__(self, value):
        self.data = value
        self.next = None
        self.prev = None


class DoubleLinkedList:
    def __init__(self):
        self.head = None # no need for tail as always the next pointer of last object will remain as none

    def list_add(self, value):
        node = Node(value)   # make new node
        # self.head is either pointing to None or the first object, make the next pointer of the new node point to the same
        node.next = self.head
        # if head is not null, than there is other items in the list
        if self.head is not None:
            # make the prev pointer of the node that head is pointing to point to the new node
            self.head.prev = node
        # make the head point to the new node
        self.head = node
        # make prev pointer of new node, point to head
        node.prev = self.head

    def list_search(self, value):
        # start from the head
        p = self.head
        # do it as long as there is no pointer and value not foun
        while p is not None:
            # make p reference to next node
            if p.data is not None:
                if p.data == value:
                    return p
            if p.next is not None:
                p = p.next
            else:
               return False

    def list_delete(self, value):
        # find the node in the linked list
        p = self.list_search(value)
        # if what back pointer points to is not head
        if p.prev is not None:
            # make the next pointer of the node behind, point to the back of the node ahead
            p.prev.next = p.next
        else:
            # if the back node is the head, make it point to the node after
            self.head = p.next
            # if there is a node after
        if p.next is not None:
            p.next.prev = p.prev  # make the the back pointer of the node ahead point to the front pointer of the node behind

    def __iter__(self):
        node = self.head
        while node:
            yield node
            node = node.next

    def get_top(self):
        return self.head

Test code:

from double_linked_list import DoubleLinkedList as linked_list


def main():
    print("----------------------")
    print("Test Add")
    my_list = linked_list()
    my_list.list_add(1)
    my_list.list_add(2)
    my_list.list_add(3)
    my_list.list_add(4)

    for i in my_list:
        print(i.data)

    print("----------------------")
    print("Test Delete")


    my_list.list_delete(3)

    for i in my_list:
        print(i.data)

    print("----------------------")
    print("Test Top get method")
    print(my_list.get_top().data)


if __name__ == "__main__":
    main()

Result:

----------------------
Test Add
4
3
2
1
----------------------
Test Delete
4
2
1
----------------------
Test Top get method
4

EDIT: Boundary condition and comparison fix

classes:

class Node:
    def __init__(self, value):
        self.data = value
        self.next = None
        self.prev = None


class DoubleLinkedList:
    def __init__(self):
        self.head = None # no need for tail as always the next pointer of last object will remain as none

    def list_add(self, value):
        node = Node(value)   # make new node
        # self.head is either pointing to None or the first object, make the next pointer of the new node point to the same
        node.next = self.head
        # if head is not null, than there is other items in the list
        if self.head is not None:
            # make the prev pointer of the node that head is pointing to point to the new node
            self.head.prev = node
        # make the head point to the new node
        self.head = node
        # make prev pointer of new node, point to head
        node.prev = self.head

    def list_search(self, value):
        # start from the head
        p = self.head
        # do it as long as there is no pointer and value not foun
        while p is not None:
            # make p reference to next node
            if p.next is not None:
                if p.data == value:
                    return p
                p = p.next
            else:
                 return 0

    def list_delete(self, value):
        # find the node in the linked list
        p = self.list_search(value)
        # if what back pointer points to is not head
        if p != 0:
            if p.prev is not None and p != self.head:
                # make the next pointer of the node behind, point to the back of the node ahead
                p.prev.next = p.next
            else:
                # if the back node is the head, make it point to the node after
                self.head = p.next
                # if there is a node after
            if p.next is not None:
                p.next.prev = p.prev  # make the the back pointer of the node ahead point to the front pointer of the node behind
            return True
        else:
            return False

    def __iter__(self):
        node = self.head
        while node:
            yield node
            node = node.next

    def get_top(self):
        return self.head

test file:

from double_linked_list import DoubleLinkedList as linked_list


def main():
    print("----------------------")
    print("Test Add")
    my_list = linked_list()
    my_list.list_add(1)
    my_list.list_add(2)
    my_list.list_add(3)
    my_list.list_add(4)
    my_list.list_add(-200000)
    my_list.list_add('a')
    my_list.list_add(50000000)
    my_list.list_add(50)

    for i in my_list:
        print(i.data)

    print("----------------------")
    print("Test Delete")


    test_delete = my_list.list_delete(50000000)
    if test_delete:
        print("success")
    else:
        print("fail")

    test_delete = my_list.list_delete(50)
    if test_delete:
        print("success")
    else:
        print("fail")

    test_delete = my_list.list_delete('a')
    if test_delete:
        print("success")
    else:
        print("fail")


    print("%%%%%%%%%%%%%%%%%%%%")

    for i in my_list:
        print(i.data)

    print("----------------------")
    print("Test Top get method")
    print(my_list.get_top().data)


if __name__ == "__main__":
    main()
\$\endgroup\$
7
\$\begingroup\$

First - and important thing:

while p is not None and p.data is not value:

You comparison p.data is not value is something different from p.data != value - and I guest that you wanted the second.

is means the same object, while == means the same value (of optionally different objects). For small integers - as in your test - Python uses the same predefined object but for e. g. 500 or -50 it is not true - try in your interpreter

500 + 1 is 501

and you will obtain False.


Second, you need not compare to None (or to 0, or to '', etc.) as its boolean value is False. So the same command - in this case the correct one - may be

while not p and p.data != value:

(and similarly for your other commands).

\$\endgroup\$
  • \$\begingroup\$ for example instead of if self.head is not None , i should write if not self.head? \$\endgroup\$ – BlooB Aug 22 '17 at 22:10
  • \$\begingroup\$ when i change the while loop to suggested, compilation fails and following error is thrown AttributeError: 'NoneType' object has no attribute 'prev' \$\endgroup\$ – BlooB Aug 22 '17 at 22:14
  • \$\begingroup\$ IT happens when i change p is not None to not p \$\endgroup\$ – BlooB Aug 22 '17 at 22:30
  • 1
    \$\begingroup\$ Using not variable instead variable is not None has one caveat - if the variable is able to reach one of the values False, numeric zero, empty strings or empty containers (tuples, lists, dictionaries, ...), they are evaluated as False, too. (For objects you have to define the __bool__() or __len__() method in their classes to be interpreted themselves as False.) \$\endgroup\$ – MarianD Aug 23 '17 at 16:07
  • 1
    \$\begingroup\$ Changing your while loop to suggested ... - I guess it reveals some mistake in your code. \$\endgroup\$ – MarianD Aug 23 '17 at 16:10
2
\$\begingroup\$

In your test file you may substitute the part

print("----------------------")
print("Test Add")
my_list = linked_list()
my_list.list_add(1)
my_list.list_add(2)
my_list.list_add(3)
my_list.list_add(4)
my_list.list_add(-200000)
my_list.list_add('a')
my_list.list_add(50000000)
my_list.list_add(50)

with

print(22 * '-')
print("Test Add")
my_list = linked_list()
elements = (1, 2, 3, 4, -200000, 'a', 500000000, 50)
for elem in elements:
    my_list.list_add(elem)

and - similarly - the part

test_delete = my_list.list_delete(50000000)
if test_delete:
    print("success")
else:
    print("fail")

test_delete = my_list.list_delete(50)
if test_delete:
    print("success")
else:
    print("fail")

test_delete = my_list.list_delete('a')
if test_delete:
    print("success")
else:
    print("fail")

with

elements = (50000000, 50, 'a')
for elem in elements:
    test_delete = my_list.list_delete(elem)
    if test_delete:
        print("success")
    else:
        print("fail")

Still would be better to use the Unit testing instead - e. g. standard Python unittest module (see Unit testing framework).

\$\endgroup\$
  • \$\begingroup\$ Than you, I have never used the testing framework. I am looking at the documentation as i am writing this comment \$\endgroup\$ – BlooB Aug 23 '17 at 17:10
2
\$\begingroup\$

list_search (and so does list_delete) does not handle the 'not found' case. this went unnoticed as you did not write a test. So the main point is - if you write a library class/function it is mandatory to do good tests. full code coverage and all regular and edge cases you can think of. python provides a unit test framework, use it.


EDIT: also, from a design point it is strange that get_top and __iter__ are returning nodes instead of values. you should get returned what you insert.


EDIT: in your second version you use 0 as return value for a not successful search. you should use None instead as this is what you use in prev and next attributes. this would also simplify your code.

def list_search(self, value):
    # start from the head
    p = self.head
    # do it as long as there is no pointer and value not foun
    while p is not None and p.data != value:
        # make p reference to next node
        p = p.next
    return p

in delete you test for None

def list_delete(self, value):
    # find the node in the linked list
    p = self.list_search(value)
    # if what back pointer points to is not head
    if p is not None:
    ...
\$\endgroup\$
  • \$\begingroup\$ list_search returns None if it is not found, doesn't that cover it? \$\endgroup\$ – BlooB Aug 22 '17 at 22:26
  • \$\begingroup\$ says who? a testcase? \$\endgroup\$ – stefan Aug 22 '17 at 22:36
  • \$\begingroup\$ I did see the issue. thank you for pointing it out. as the second part, for what i am doing i do need to pass the node as a whole. \$\endgroup\$ – BlooB Aug 22 '17 at 23:18
  • \$\begingroup\$ So you pass test my_list.list_delete(42) now? What about my_list.list_delete(4)? As for passing nodes outside - i doubt you need to. this is most probably a design problem. where do you need to read nextattribute outside when you already implemented __iter__? and manipulating nextoutside is an absolute no go. \$\endgroup\$ – stefan Aug 22 '17 at 23:26
  • \$\begingroup\$ Than you, I have never used the testing framework. I am looking at the documentation as i am writing this comment and will change the testing side \$\endgroup\$ – BlooB Aug 23 '17 at 17:11

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.