Linked list without sentinels

Question

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

Answer 1

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

Answer 2

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

Answer 3

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