# by default, only the result of the last expression in a cell is displayed after evaluation.
# the following forces display of *all* self-standing expressions in a cell.
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
LinkedList and Node classes¶class LinkedList:
class Node:
def __init__(self, val, next=None):
self.val = val
self.next = next
def __init__(self):
self.head = None
self.count = 0
def prepend(self, value): #O(1) better than arrayList O(n) prepend
self.head = self.Node(value, self.head)
self.count+=1
def __len__(self):
return self.count
def __iter__(self):
n = self.head #n is just a local variable to walk the list
while n:
yield n.val
n = n.next
def __repr__(self):
return '[' + ', '.join(str(x) for x in self) + ']'
lst = LinkedList()
for i in range(10):
lst.prepend(i)
lst
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
append¶class LinkedList (LinkedList): # note: using inheritance to extend prior definition
def append(self, value):
#need a special case for empty list (self.head is None)
if not self.head:
self.prepend(value)
else:
n=self.head
while n.next:
n=n.next
# got out of loop because n.next is None
n.next = self.Node(value, None)
self.count+=1
# BAD O(n) all calls
lst = LinkedList()
for i in range(10):
lst.append(i)
lst
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
class LinkedList (LinkedList):
def __init__(self): # new constructor for linkedlist
self.head = self.tail = None
self.count = 0
def prepend(self, value): #O(1)
self.head = self.Node(value, self.head)
self.count+=1
if not self.tail: # the linked list must have been empty
# the head and the tail are the same Node
self.tail=self.head
def append(self, value): #O(1)
if self.count==0: # special case list is empty
self.prepend(value)
else:
# self.tail is pointer to last node, its .next is None
self.tail.next=self.Node(value, None)
self.tail=self.tail.next
self.count+=1
lst = LinkedList()
for i in range(10):
lst.append(i)
lst
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
lst1 = LinkedList()
for i in range(10):
lst1.prepend(i)
lst1
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
class LinkedList (LinkedList):
def del_head(self): #O(1)
assert(len(self) > 0)
self.head=self.head.next
self.count-=1
if self.count==0:
self.tail=None
lst = LinkedList()
for i in range(10):
lst.append(i)
lst.del_head()
lst.del_head()
lst
[2, 3, 4, 5, 6, 7, 8, 9]
lst.del_head()
lst.del_head()
lst.del_head()
lst.del_head()
lst.del_head()
lst.del_head()
lst.del_head()
lst.del_head()
lst
[]
lst.del_head()
--------------------------------------------------------------------------- AssertionError Traceback (most recent call last) <ipython-input-9-36c347e456f7> in <module> ----> 1 lst.del_head() <ipython-input-6-9caf6ce2482e> in del_head(self) 1 class LinkedList (LinkedList): 2 def del_head(self): ----> 3 assert(len(self) > 0) 4 self.head=self.head.next 5 self.count-=1 AssertionError:
class LinkedList (LinkedList): #O(n)
def del_tail(self):
assert(len(self) > 0)
if self.count==1:
self.head=None
self.tail=None
self.count=0
else:
n=self.head
while n.next !=self.tail: # while n.next is not the tail
n=n.next
# n points to the node before the tail
self.tail=n
self.tail.next=None
self.count-=1
lst = LinkedList()
for i in range(5):
lst.append(i)
lst.del_tail()
lst.del_tail()
lst
[0, 1, 2]
lst.del_tail()
lst.del_tail()
lst.del_tail()
lst
[]
class LinkedList:
class Node:
def __init__(self, val, prior=None, next=None):
self.val = val
self.prior = prior
self.next = next
def __init__(self): # linkedlist consturctor
self.count = 0
self.head=LinkedList.Node(None) #dummy node
self.head.next=self.head
self.head.prior=self.head
def prepend(self, value): # works even if list is empty becuase we have the dummy node
self.count += 1
# val prior next
n=LinkedList.Node(value,self.head, self.head.next) #self.head is before this new node
#self.head.next is waht used to be after the self.head
self.head.next.prior=n
self.head.next=n
#O(1)
def append(self, value):
self.count += 1
# val prior next
n=LinkedList.Node(value,self.head.prior, self.head)
# self.head.prior is the old last node
self.head.prior.next=n
self.head.prior=n
def __getitem__(self, idx): # O(N)
assert idx >= 0 and idx < len(self) # BETTER, NORMALIZE INDEX FIRST
# checking for valid index within the size of the linked list
# walk to idx item
# I know there is at least 1 item inthe linked list, so self.head.next points
# to that first item (index position zero)
n=self.head.next
for i in range(idx):
n=n.next
return n.val
def del_head(self):
assert(len(self) > 0)
to_del=self.head.next #pointer to the node I want to delete
to_del.next.prior=to_del.prior # node after the to_del point to the node before the to_del node
to_del.prior.next=to_del.next
self.count-=1
# these last 3 statements can be used to delete any node in the linkedlist
def __len__(self):
return self.count
def __iter__(self):
n = self.head.next
while n is not self.head:
yield n.val
n = n.next
def __repr__(self):
return '[' + ', '.join(str(x) for x in self) + ']'
lst = LinkedList()
for i in range(5):
lst.prepend(i)
for i in range(5):
lst.append(i)
lst
[4, 3, 2, 1, 0, 0, 1, 2, 3, 4]
lst[0]
lst[5]
4
0
lst.del_head()
lst
[3, 2, 1, 0, 0, 1, 2, 3, 4]
class LinkedList:
class Node:
def __init__(self, val, prior=None, next=None):
self.val = val
self.prior = prior
self.next = next
def __init__(self): # linkedlist consturctor
self.count = 0
self.head=LinkedList.Node(None) #dummy node
self.head.next=self.head
self.head.prior=self.head
self.cursor=self.head #initially the cursor is pointing to dummy node
def prepend(self, value): # works even if list is empty becuase we have the dummy node
self.count += 1
# val prior next
n=LinkedList.Node(value,self.head, self.head.next) #self.head is before this new node
#self.head.next is waht used to be after the self.head
self.head.next.prior=n
self.head.next=n
#O(1)
def append(self, value):
self.count += 1
# val prior next
n=LinkedList.Node(value,self.head.prior, self.head)
# self.head.prior is the old last node
self.head.prior.next=n
self.head.prior=n
def __getitem__(self, idx): # O(N)
assert idx >= 0 and idx < len(self) # BETTER, NORMALIZE INDEX FIRST
# checking for valid index within the size of the linked list
# walk to idx item
# I know there is at least 1 item inthe linked list, so self.head.next points
# to that first item (index position zero)
n=self.head.next
for i in range(idx):
n=n.next
return n.val
def del_head(self):
assert(len(self) > 0)
to_del=self.head.next #pointer to the node I want to delete
to_del.next.prior=to_del.prior # node after the to_del point to the node before the to_del node
to_del.prior.next=to_del.next
self.count-=1
# these last 3 statements can be used to delete any node in the linkedlist
def __len__(self):
return self.count
def __iter__(self):
n = self.head.next
while n is not self.head:
yield n.val
n = n.next
def __repr__(self):
return '[' + ', '.join(str(x) for x in self) + ']'
def cursor_set(self, idx): #O(n)
assert idx >= 0 and idx < len(self) # add normalize index
#we know that the cursor is valid for the linked list
self.cursor=self.head.next # cursor is pointing to zero item
for i in range(idx):
self.cursor=self.cursor.next
def cursor_insert(self, value): # O(1) #insert at the cursor position, move the old cursor node down
assert self.cursor is not self.head # cursor at valid index
# value prior next
n = LinkedList.Node(value,self.cursor, self.cursor.next)
self.cursor.next.prior=n
self.cursor.next=n
self.cursor=n
self.count+=1
def cursor_delete(self): # O(1)
assert self.cursor is not self.head
n=self.cursor
self.cursor=self.cursor.next
if self.cursor == self.head: #dummy node
self.cursor=self.cursor.next
n.prior.next = n.next
n.next.prior = n.prior
self.count-=1
lst = LinkedList()
for i in range(10):
lst.append(i)
lst
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
lst.cursor_set(4)
for x in 'abcd':
lst.cursor_insert(x)
lst
[0, 1, 2, 3, 4, a, b, c, d, 5, 6, 7, 8, 9]
lst.cursor_set(8)
#lst.cursor.val
for _ in range(4):
lst.cursor_delete()
lst
[0, 1, 2, 3, 4, a, b, c, 8, 9]
Run-time complexities for circular, doubly-linked list of $N$ elements:
Lab 5, 1.Subscript-based access (if time permits)