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

• Solomon Ucko: Spreadsheet I made with efficiencies: docs.google.com/spreadsheets/d/…

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

• BlooB: for example instead of if self.head is not None , i should write if not self.head?
• BlooB: when i change the while loop to suggested, compilation fails and following error is thrown AttributeError: 'NoneType' object has no attribute 'prev'
• BlooB: IT happens when i change p is not None to not p
• MarianD: 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.)
• MarianD: Changing your while loop to suggested ... - I guess it reveals some mistake in your code.

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

• BlooB: Than you, I have never used the testing framework. I am looking at the documentation as i am writing this comment

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

• BlooB: list_search returns None if it is not found, doesn't that cover it?
• stefan: says who? a testcase?
• BlooB: 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.
• stefan: 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.
• BlooB: 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