I wrote two functions:
swapsingle(): swaps elements in a singly linked list
swapdouble(): swaps elements in a doubly linked list
But the book I am reading (Data Structures and Algorithms in Python - Michael H. Goldwasser, Michael T. Goodrich, and Roberto Tamassia) says that the swapping in a doubly linked list should be faster than the one in a singly linked list. But when I time both functions swapdouble() is slower
Here are my two single and double linked classes:
class SingleLL:
""" Singly Linked List Class """
# Nested _Node class
class _Node:
__slots__ = '_element', '_next'
def __init__(self, element, next):
self._element = element
self._next = next
def __init__(self):
""" Create an empty Stack"""
self._head = None # Reference to the Head node
self._size = 0
def __len__(self):
""" Returns the number of elements in the stack"""
return self._size
def push(self, e):
""" Add element e to the top of the stack"""
self._head = self._Node(e, self._head)
self._size += 1
def __str__(self):
""" Printing a Linked List"""
# defining a blank result variable
result = ""
# initialising the printer to head
printer = self._head
# traversing and adding it to result
while printer:
result += str(printer._element) + ", "
printer = printer._next
# removing the trailing comma
result = result.strip(', ')
# before printing we check if the list is empty or not
if len(result):
return "[" + result + "]"
else:
return "[]"
class DoubleLL:
"""A base class providing a doubly linked list representation"""
class _Node:
"""Lighweight, non-public class for storing a doubly linked node."""
__slots__ = '_element', '_prev', '_next'
def __init__(self, element, prev, next):
self._element = element
self._prev = prev
self._next = next
def __init__(self):
""" Create an empty list"""
self._header = self._Node(None,None,None)
self._trailer = self._Node(None, None, None)
self._header._next = self._trailer
self._trailer._prev = self._header
self._size = 0
def __len__(self):
return self._size
def _insert_between(self,e, predecessor, successor):
""" Add element e between two existing nodes and return new node."""
newest = self._Node(e,predecessor,successor)
predecessor._next = newest
successor._prev = newest
self._size += 1
#return newest
def push(self, e):
""" Add element e to the front of the list"""
self._insert_between(e,self._header, self._header._next)
def __str__(self):
""" Printing a Linked List"""
# defining a blank result variable
result = ""
# initialising the printer to head
printer = self._header
# traversing and adding it to result
while printer:
result += str(printer._element) + ", "
printer = printer._next
# removing the trailing comma
result = result.strip(', ')
# before printing we check if the list is empty or not
if len(result):
return "[" + result + "]"
else:
return "[]"
and here is the code for my two functions with a test case and timing:
def swapsingle(L,a,b):
if a == b:
return
else:
# let's look for the node with 'a' as an element
preva = None
loca = L._head
while loca._next != None and loca._element != a:
preva = loca
loca = loca._next
# let's look for the node with 'b' as an element
prevb = None
locb = L._head
while locb._next != None and locb._element != b:
prevb = locb
locb = locb._next
# if either 'a' or 'b' is not on the linked list, do nothing
if loca == None or locb == None:
return
# if 'a' is not the head of the list
if preva != None:
preva._next = locb
else:
L._head = locb
# if 'b' is not the head of the list
if prevb != None:
prevb._next = loca
else:
L._head = loca
# swap next pointers
temp = loca._next
loca._next = locb._next
locb._next = temp
def swapdouble(L,a,b):
if a == b:
return
else:
# let's look for 'a'
loca = L._header
while loca._next != None and loca._element != a:
loca = loca._next
# let's look for 'b'
locb = L._header
while locb._next != None and locb._element != b:
locb = locb._next
# if either 'a' or 'b' are not on the list, do nothing
if loca == None or locb == None:
return
# change prev
temp = loca._prev
loca._prev = locb._prev
locb._prev._next = loca
locb._prev = temp
temp._next = locb
# change next
temp = loca._next
loca._next = locb._next
locb._next._prev = loca
locb._next = temp
temp._prev = loca
L = SingleLL()
for i in range(1,5):
L.push(i)
print(L)
%timeit swapsingle(L,1,3)
print(L)
D = DoubleLL()
for i in range(1,5):
D.push(i)
print(D)
%timeit swapdouble(D,1,3)
print(D)
Here is my output:
[4, 3, 2, 1]
844 ns ± 10.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
[4, 1, 2, 3]
[None, 4, 3, 2, 1, None]
1.12 µs ± 2.83 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
[None, 4, 1, 2, 3, None]
Can you please explain to me why my doubleswap is slower than singleswap, and why it should be faster in the first place?
I think the statement speaks about swapping two nodes given only references to the nodes, not their values (which may not even be unique). Then it's fairly obvious: In case of doubly-linked list, you have pointers to both predecesors and succesors of the swapped nodes, so you can just swap them. In case of singly-linked list you first have to iterate through the list to find the predecessors.