complete: Double linked list python
Update 9-2-19: Reformatting how blogger displays the code. --Also included pytest file at the bottom, after the Double Linked List code block.
I tried to make the comments explain as much as possible. The print out method I made,
'graphical()' helped a TON debugging as I went.
SO here it is. And as always, if for some reason some one see's this, I'm new, I'm learning... I hope it helps someone, that's my goal... and if you want me to improve it, I'd be happy to, drop me a note or something!
update 12-8-2017 attach-node() and use in insert() are at the bottom. I didn't change the original in case someone wanted to see how to do it the long way round.
update 12-19-17 swap method, swap two node positions, must be next to each other in the list
update 12-22-17 swap any nodes, anywhere in the list. ((uses swap_left for nodes next to each other)). Added at bottom. Update 12-23 bug with node1/node2 prev.... fix added in.
update 12-25-17 swap_left() has a -- set_sides(node1,node2) method added, and now can swap if list only has two items, an end and begin node
update 12-30-17 remove() and detach_node() now solely uses the updated detach_node() to take the node out of the list. Fixed some of my original commentary... and dump() now does what it was supposed to and prints list instead of empty it.
update 1-14-18 __init__ now has an attribute _length, and uses that instead of the
count() method to keep track of the size of the list. Tested with pytest, and manually with the list's graphical() and different removal methods
--- code block ----
---end code block---
Code block for the pytest file:
-- pytest code block--
--end pytest code block --
I tried to make the comments explain as much as possible. The print out method I made,
'graphical()' helped a TON debugging as I went.
SO here it is. And as always, if for some reason some one see's this, I'm new, I'm learning... I hope it helps someone, that's my goal... and if you want me to improve it, I'd be happy to, drop me a note or something!
update 12-8-2017 attach-node() and use in insert() are at the bottom. I didn't change the original in case someone wanted to see how to do it the long way round.
update 12-19-17 swap method, swap two node positions, must be next to each other in the list
update 12-22-17 swap any nodes, anywhere in the list. ((uses swap_left for nodes next to each other)). Added at bottom. Update 12-23 bug with node1/node2 prev.... fix added in.
update 12-25-17 swap_left() has a -- set_sides(node1,node2) method added, and now can swap if list only has two items, an end and begin node
update 12-30-17 remove() and detach_node() now solely uses the updated detach_node() to take the node out of the list. Fixed some of my original commentary... and dump() now does what it was supposed to and prints list instead of empty it.
update 1-14-18 __init__ now has an attribute _length, and uses that instead of the
count() method to keep track of the size of the list. Tested with pytest, and manually with the list's graphical() and different removal methods
--- code block ----
class DLLNode(object):
# I changed the order so that it would be easier to visualize
# and easier to keep track of.
def __init__(self, prev, value, nxt):
# the first node will have no next or previous
self.value = value
self.next = nxt
# previous
self.prev = prev
def __repr__(self): # [ <--- prev , DATA , next ---> ]
nval = self.next and self.next.value or None
pval = self.prev and self.prev.value or None
## previous node, assigned value, link to next node in list ##
return f"[{repr(pval)}, {self.value}, {repr(nval)}]"
class DLList(object):
## initiate ##
def __init__(self):
# end holds the last node, and after the list is greater then 1 the whole list
# through it's previous links
self.end = None
# begin holds the first node, and the whole list through it's next links
self.begin = None
self._length = 0
## END initiate ##
########## PUSH (aka : ADD/APPEND) ################
def push(self, obj):
# if there is an empty list create first node with no next or prev.
if self.end == None and self.begin == None:
newnode = DLLNode(None, obj, None)
self.begin = newnode
self._length += 1
# I want it to also print something off like
## ( (--) , 1 , (--) ) ## when it prints the list.....
# did this in 'my print out methods' method: graphical()
## if the list has contents, I never want the begin and end to be equal.
elif self.end == None and self.begin != None:
# get the address of the original node
node = self.begin
# create address for new node
newnode = DLLNode(node, obj, None)
self.end = newnode
self.begin.next = self.end
self._length += 1
else:
#[ <--- , DATA, (/)]
node = self.end
#[<-node---, DATA, (/) ] [self.end, obj, None]
newnode = DLLNode(node, obj, None)
# at this point the list has at least 2 items... the begin is pointing to the next item
# which if with 2 items is the end node. We only need to change the end node. Begin node
# does not need to be altered.
# change end node TO -->
# change self.end next [ <--*---, DATA, -- newnode --> ]
# * it doesn't matter what this link is. IT's set a long time ago.
self.end.next = newnode
# Now I set the end = to the newnode that is pushed on
# self.end = [ <--- old self.end, DATA, (/) ] (newnode)
self.end = newnode
self._length += 1
assert self.end != self.begin
################## END PUSH ######################
################## PUSH NODE.... ##################
# pass in data of node into list... useless???############
def push_node(self, node):
### if original node is passed in, it will be altered! ####
print("activate push node")
# passing in a node part of a list your using, will alter the original node.
# must create a new DLLNode to pass in to keep original from being altered.
# if there is an empty list create first node with no next or prev.
if self.end == None and self.begin == None:
node.prev = None
node.next = None
self.begin = node
elif self.end == None and self.begin != None:
# get the address of the original node
oldnode = self.begin
# create address for new node
node.prev = None
node.next = self.begin
self.end = self.begin
self.end.prev = node
self.begin = node
#print(self.end)
#print(self.begin)
else:
print("pushing node")
#[ <--- , node , (/)]
node.next = None
node.prev = self.end
self.end.next = node
self.end = node
assert self.end != self.begin
#################----------------------------------##############
####### MY PRINT OUT METHODS #########
###( <--- previous, obj , next --->)###
def graphical(self):
## graphical uses the prev, to go through the list.
## so it's like an invariant check..................
## None = (/)
## [ link = node in list ]
## OBJ = (data count)DATA?
## [ prev 2 , third data, next none ]
## so, [ <---2 , (3) DATA , (/) ]
length = self._length
node = self.begin
if self.begin == None:
print(" EMPTY ")
elif self.begin != None and self.end == None:
print("\n\n")
# [(/), (0) DATA, (/)]
print(f"{node.value}=")
print(f"[(/), (0) DATA, (/)]")
else:
node = self.end
#I only modify length to keep track
if node:
print("\n\n")
while node:
# example, length is 3
if node.next == None and node.prev != None:
# [ <--2 , (3)DATA , (/) ]
print(f"{node.value}=")
print(f"\t [<-- {length -1}, ({length})DATA , (/) ]")
elif node.next != None and node.prev != None:
# [ <--1, (2)DATA , 3-->]
print(f"{node.value}=")
print(f"\t [<-- {length -2}, ({length-1})DATA, {length}-->]")
length -= 1
else:
# [ (/), (1)DATA , 2-->]
print(f"{node.value}=")
print(f"\t [ (/), (1)DATA, 2--> ]")
node = node.prev
######## <------ prev ---- end
def what_end(self):
node = self.end
if node:
print(" end = ")
while node:
print(node)
node = node.prev
######## begin -----> next
def where_begin(self):
node = self.begin
print(" front = ")
chain = f"[ "
if node:
while node:
if node.next != None:
chain = chain + (f"{node.value}, ")
node = node.next
else:
chain = chain + (f"{node.value}]")
node = node.next
print(chain)
################### END my print outs #################################
################################## count ######################################
def count(self):
# replaced with self._length, but still used in _invariant
count = 0
node = self.begin
while node:
count += 1
node = node.next
return count
################################ END count ###################################
############################## POP ############################################
def pop(self):
# Zed said it would be just like SLL.....
# [ (/) , DATA , ---->] [<----, DATA, ---->] [<----, DATA, (/)]
# [ (/) , DATA , ---->] [<----, DATA, (/) ] ....................
# if list is empty:
if self.begin == None:
print(" Nothing to PoP! ")
return None
elif self.begin and not self.end:
print(" That was a lonely little data...")
carrots = self.begin.value
self.begin = None
self._length = 0
return carrots
else:
carrots = self.end.value
newEnd = self.end.prev
self.end = newEnd
if newEnd == self.begin:
self.begin.next = None
self.end = None
newEnd.next = None
self._length -= 1
return carrots
########################## END POP #####################
#####################------------------------------------############
################# -- GET -- and it's reverse lookup _get #####
####################-------------------------------------#############
def get(self, index):
#print("GET ACTIVATED.... checking hash_key activated.")
index = int(index)
length = self._length
count = 0
if length == 0:
# for testing, None works better then "Empty list!"
return None
elif index >= (length):
print(" index out of range! ")
# this should be an error for the real thing
# pytest for raise error is a pain in the ass....
#raise IndexError
return None
else:
count = 0
node = self.begin
while node:
#print(f"while loop.{count}")
if count == index:
#print('get return value:')
#print(node.value)
return node.value
node = node.next
count += 1
def _get(self, index):
length = self.count()
if length == 0:
print(" ***** Empty list ***** ")
return(None)
elif index >= (length):
print(" index out of range! ")
return None
elif length == 1:
# when there are 0, or 1 item's on the list, else loop won't work.
if index == 0:
node = self.begin
return(node.value)
else:
node = self.end
# [(/)(0)DATA -->][<---(1)DATA--->][<---(2)DATA--->][<---(3)DATA (/) ]
# length 1 2 3 4
while node:
if length == index + 1:
return(node.value)
else:
node = node.prev
length -= 1
####################### END GET ##########################
########################### invariant #########################
# the things that need to hold true on every change to the list
def _invariant(self):
node = self.begin
length = self.count()
if node == None:
assert length == self._length
assert self.end == None
elif length == 1:
assert length == self._length
assert node.next == None
assert node.prev == None
assert self.end == None
else:
assert length == self._length
assert self.end != self.begin
assert self.end.next == None
assert self.begin.prev == None
############# END _invariant ##########################
# what python does when it removes from a list :
#bogs = ['pop', 'soda', 'pop', 'coke', 'pepsi', 'milk']
#bogs.remove('pop')
#print(bogs)
# result = ['pop', 'soda', -- , 'coke', 'pepsi', 'milk']
# python doesn't remove by index from the list.
# so it will remove from the back to front, the first 'pop' it finds....
################# Remove ########################
# [(/), 1DATA , 2--->][<---1, 2DATA 3--->][<----2, 3DATA, (/)]
# [(/), 1DATA , 3--->][<---1 3DATA, (/)]
def remove(self, obj):
# my original remove had a ton of stuff in it....
# I should have kept it to show the long way round....
# removing the entire node is a much better option. These Nodes as I've learned can
# grow to contain TONS of stuff... I had no idea there was a fast way round till now.
head = self.begin
#tail = self.end
while head:
if head.value == obj:
result = head.value
self.detach_node(head)
self._length -= 1
return result
#testing return result
break
head = head.next
########################### END remove ######################
def detach_node(self, node):
### node ### [ <---1 , 2DATA , 3---> ] ### node ###
# [(/), 1DATA , ((2--->))][**<---1**, 2DATA** 3--->**](([<----2)))), 3DATA, (/)]
# [(/), 1DATA , 3--->][<---1 3DATA, (/)]
if node.prev == None and node.next == None:
## working with Dictionary.... detach nodes...
## one node on the list
self.begin = None
self.end = None
elif node.prev == None and node.next != None:
# node is a begin node:
#[(/) node ---next-->][<----new---->]
newnode = node.next
if newnode.next != None:
# newnode is not the end node
self.begin = newnode
self.begin.prev = None
else:
# newnode is the end node
# two items on list
self.begin = newnode
self.end = None
self.begin.prev = None
elif node.next == None and node.prev != None:
# node is an end node:
# [<---new ---node ---->][<--new--- node (/)]
newend = node.prev
if newend.prev == None:
## newend is the begin node
## two items on list
self.end = None
self.begin.next = None
else:
## node is end node
## more then two on list
self.end = newend
self.end.next = None
else:
## item in the middle of list.
## not begin or end node
prevlink = node.prev # <---1
#[(**<---1**), 2DATA, 3-->]
nextlink = node.next # ---> 3
#[(<---1, 2DATA, (**3--->**))]
#node.prev.next = 2--->
#[(/), 1DATA, ((**2--->**))]
# nextlink == ----> 3
node.prev.next = nextlink
#node.next.prev = <----2
# [**<---2**, DATA3, (/)]
# prevlink == <-----1
node.next.prev = prevlink
################## END detach_node ################
#### someone in class, and my sister helped me realize
## that in sorting this list, I need to exchange the entire node
## not just the data..... #####################
######### swap nodes left ###############
def swap_left(self, node1, node2):
# or NONE left right or NONE
#spam-[NONE-ARC--n1-->][<-abc-node1--n2--->][<--n1---node2---lvx->][<--n2---RUM or NONE]
#eggs-[NONE ARC--n2-->][<-abc-node2--n1--->][<--n2---node1---lvx->][<--n1--RUM or NONE]
# 3 6 ? 5 4
#node1prev, node1next, node2prev, node2next = set_sides(node1,node2)
def set_sides(node1, node2):
if node1.prev != None:
node1prev = node1.prev
else:
node1prev = None
if node1.next != None:
node1next = node1.next
else:
node1next = None
if node2.prev != None:
node2prev = node2.prev
else:
node2prev = None
if node2.next != None:
node2next = node2.next
else:
node2next = None
return node1prev, node1next, node2prev, node2next
node1prev, node1next, node2prev, node2next = set_sides(node1,node2)
if node1prev != None and node1next != None and node2prev != None and node2next != None:
print(" swap 1 ")
#### get addresses#####
prevnode1 = node1.prev
prevnode2 = node2.prev
#nextnode1 = node1.next
#nextnode2 = node2.next
if prevnode1 == node2: ### eggs -
#node1.next = node2
#node2.prev = node1
print(" eggs ")
oldARC = node2.prev
node2.prev.next = node1
oldRUM = node1.next
node1.next.prev = node2
node1.prev = oldARC
node2.next = oldRUM
node1.next = node2
node2.prev = node1
#oldARC.next = node2
#oldRUM.prev = node1
print(node1)
print(node2)
elif prevnode2 == node1:
print("spam") ### spam-
#node1.prev = node2
#node2.next = node1
oldARC = node1.prev
node1.prev.next = node2
node2.prev = oldARC
oldRUM = node2.next
node2.next.prev = node1
node1.next = oldRUM
node2.next = node1
node1.prev = node2
#print(f"oldArc = {oldARC}")
#print(f"oldRUM = {oldRUM}")
#print(node1)
#print(node2)
else:
print(" THESE nodes can not be swapped with swap_left! ")
elif node1.prev == None and node2.next == None:
print(" swap begin (node1) and end node (node2). ")
# node1 is begin, node2 is end
self.begin = node2
self.end = node1
node2.prev = None
node1.next = None
node2.next = node1
node1.prev = node2
elif node2.prev == None and node1.next == None:
print(" swap begin (node2) and end node (node1). ")
self.begin = node1
self.end = node2
node1.prev = None
node2.next = None
node1.next = node2
node2.prev = node1
elif node1.prev == None and node2.next != None:
print("swap 2 (begin node) ")
### this one works!!! WOOT! ###
# or NONE left right or NONE
#[NONE----node1--n2--->][<--n1---node2---lvx->][<--n2---lvx or NONE]
#[NONE----node2--n1--->][<--n2---node1---lvx->][<--n1---lvx or NONE]
# if node1 prev is none... node1 is begin.
self.begin = node2
nlink = node2.next
node2.prev = None
node2.next = node1
node1.prev = node2
node1.next = nlink
nlink.prev = node1
elif node2.next== None and node1.next != None:
print(" swap 3 (end node)")
### node2 is the end of the list:
##[<--plink---- node1 --- n2 ---->][ <---n1-- node2-- NONE]
##[<--plink---- node2 --- n1 ---->][ <---n2-- node1-- NONE]
self.end = node1
plink = node1.prev
node1.prev.next = node2
node1.next = None
node1.prev = node2
node2.next = node1
node2.prev = plink
elif node2.prev == None and node1.next != None:
print("swap (begin node) 2 - B")
# or NONE left right or NONE
#[NONE----node2--n1--->][<--n2---node1---lvx->][<--n1---lvx or NONE]
#[NONE----node1--n2--->][<--n1---node2---lvx->][<--n1---lvx or NONE]
# if node1 prev is none... node1 is begin.
self.begin = node1
nlink = node1.next
node1.prev = None
node1.next = node2
node2.prev = node1
node2.next = nlink
nlink.prev = node2
elif node1.next== None and node2.next != None:
print("swap 3 - B (end node) ")
### node2 is the end of the list:
##[<--plink---- node2 --- n1 ---->][ <---n2-- node1-- NONE]
##[<--plink---- node1 --- n2 ---->][ <---n1-- node2-- NONE]
self.end = node2
plink = node2.prev
node2.prev.next = node1
node2.next = None
node2.prev = node1
node1.next = node2
node1.prev = plink
else:
print("swap 4")
print(" this method was not designed for the nodes it was given ")
########## END swap nodes left ##########
############# swap ANY nodes #############
## this makes me a little nervous ########
def swap_any(self, node1, node2):
print(" SWAP ANY ")
#[or NONE spam -- n1-->][<---spam---node1--eggs--->][<--n1--eggs or NONE]
#[or NONE bags -- n2-->][<---bags---node2---nots-->]<---n2--nots or NONE]
### make sure they are not next to each other ###
def set_sides(node1, node2):
if node1.prev != None:
node1prev = node1.prev
else:
node1prev = None
if node1.next != None:
node1next = node1.next
else:
node1next = None
if node2.prev != None:
node2prev = node2.prev
else:
node2prev = None
if node2.next != None:
node2next = node2.next
else:
node2next = None
return node1prev, node1next, node2prev, node2next
node1prev, node1next, node2prev, node2next = set_sides(node1,node2)
if node1prev == node2 or node2prev == node1 or node1next == node2 or node2next == node1:
## might have to fix swap_left..... I think it doesn't care which order they are
self.swap_left(node1,node2)
elif node1.prev != None and node1.next != None and node2.next != None and node2.prev != None:
print(" swap any 1")
#print(node1, node2)
### not sure why this order is important...
## ohhhhh............
## you change the link by accessing it through the original node given...
## if you change that node before the address get's assigned it will assign
## a wrong address...... try to add something later to show it.
node1.prev.next = node2 #spam
node2.prev.next = node1 #bags
node1.next.prev = node2 #eggs
node2.next.prev = node1 #nots
# this was the best way to swap them without making a bunch of temporary
# variables, and assigning them out of order, or <tierd of mental melting>
# figuring out what order to put them in.
node1.prev, node2.prev = node2.prev, node1.prev
node2.next, node1.next = node1.next, node2.next
#print(node2.prev)
#print(node2, node1)
elif node1.prev == None and node2.next != None:
## node1 is a begin node:
print(" Swap begin node, node 1 .....")
#node1.prev.next = node2 #spam
node2.prev.next = node1 #bags
node2.next.prev = node1 #nots
node1.next.prev = node2 #eggs
# this might work..... even though prev is none?
node1.prev, node2.prev = node2.prev, node1.prev
node2.next, node1.next = node1.next, node2.next
self.begin = node2
#print(f"{node1}{node2}")
elif node2.prev == None and node1.next != None:
## node2 is a begin node:
print(" Swap begin node, node 2...")
node1.prev.next = node2 #spam
#node2.prev.next = node1 #bags
node1.next.prev = node2 #eggs
node2.next.prev = node1 #nots
# this was the best way to swap them without making a bunch of temporary
# variables, and assigning them out of order, or <tierd of mental melting>
# figuring out what order to put them in.
node1.prev, node2.prev = node2.prev, node1.prev
node2.next, node1.next = node1.next, node2.next
self.begin = node1
elif node1.next == None and node2.prev != None:
## node1 is an end node:
print(" node1 is end node, swap")
node1.prev.next = node2 #spam
node2.prev.next = node1 #bags
#node1.next.prev = node2 #eggs
node2.next.prev = node1 #nots
# this was the best way to swap them without making a bunch of temporary
# variables, and assigning them out of order, or <tierd of mental melting>
# figuring out what order to put them in.
node1.prev, node2.prev = node2.prev, node1.prev
node2.next, node1.next = node1.next, node2.next
#print(node1, node2)
self.end = node2
elif node2.next == None and node1.prev != None:
#node 2 is an end node:
print(" end node swap, node 2 .....")
node1.prev.next = node2 #spam
node2.prev.next = node1 #bags
node1.next.prev = node2 #eggs
#node2.next.prev = node1 #nots
# this was the best way to swap them without making a bunch of temporary
# variables, and assigning them out of order, or <tierd of mental melting>
# figuring out what order to put them in.
node1.prev, node2.prev = node2.prev, node1.prev
node2.next, node1.next = node1.next, node2.next
#print(node2, node1)
self.end = node1
elif node1.prev == None and node2.next == None:
# node1 is a begin node, node2 is an end node:
print(" swap node1 begin, node2 end ")
#node1.prev.next = node2 #spam
node2.prev.next = node1 #bags
node1.next.prev = node2 #eggs
#node2.next.prev = node1 #nots
node1.prev, node2.prev = node2.prev, node1.prev
node2.next, node1.next = node1.next, node2.next
self.end = node1
self.begin = node2
#print(f"{node1} : {node2}")
elif node2.prev == None and node1.next == None:
# node 2 is begin, node 1 is end:
print(" swap node2 begin, node1 end ...")
node1.prev.next = node2
node2.next.prev = node1
node1.prev, node2.prev = node2.prev, node1.prev
node2.next, node1.next = node1.next, node2.next
self.end = node2
self.begin = node1
else:
print(" not complete -----------")
############# some logic ##################
#[(/), (1)DATA, <----2] [ <---1 (2)DATA --->3][<---2, (3)DATA, (/)]
# this won't work for pop()
# we are only changing the next link of the node to none in pop.
#[(/), (1)DATA, <----2][<---1, (2)DATA, (/)]
#------ shift ----------
#[(/), (1)DATA, <----2][<---1, (2)DATA, ---->3][<----2, (3)DATA, (/)]
# in shift, we are changing node 2's prev. to NONE. so it won't work
# for shift either.
################# shift ##########################
def shift(self):
# shift is a reverse pop()
# check for empty list:
head = self.begin
tail = self.end
length = self.count()
if head == None:
print(" ***Empty list*** ")
return None
# check for one item in list:
elif head != None and tail == None:
print(" shift: Goodbye sunshine. ")
self.begin = None
self._length = 0
elif length == 2:
# I never want the end and begin to be equal unless the list is empty.
newnode = self.end
newnode.prev = None
self.begin = newnode
self.end = None
self._length = 1
else:
#[(/), (1)DATA, 2--->][<---1, (2)DATA, 3---> ][<---2, (3)DATA, (/)]
node = self.begin.next
#[(/), (2)DATA, 3--->][<---2, (3)DATA, (/)]
node.prev = None
self.begin = node
self._length -= 1
########## unshift is just push() #########
def unshift(self, obj):
self.push(obj)
############################################
######## Python cleans up anything that is no longer referenced ######
#### so once you set these to None.... the nodes get garbage collected ####
def dump(self):
## I had this wrong.... dump is supposed to print the contents to screen....##
print("dump")
start = self.begin
if start == None:
print(" [] ")
else:
x = "["
while start:
x = x + f"{start.value},"
start = start.next
print (x + " ]")
####### END dump ###################
######## insert ##########
####### like remove in reverse ####
def insert(self, obj, index):
# this isn't required for my class, but I want to be able to do it.
# I'm thinking inserting at the beginning, is what the unshift should do.
#[(/), (1)DATA, 2--->][<---1, (2)DATA, 3---->][<---2, (3)DATA, (/)]
# 1 [<----1, (m)DATA, 2--->] 2
#[(/), (1), m-->][<--1, (m), 2-->][<--m,(2),3-->][<--2,(3), (/)]
head = self.begin
tail = self.end
length = self.count()
# check if they are just pushing.
if index == length:
print(" pushing: push() ")
self.push(obj)
# check if they are prefixing
# I'm going to make one... prefix
elif index == 0:
print( " prefixing data: prefix() ")
self.prefix(obj)
# check if they are indexing out of range:
elif index > length:
print(" index out of range! ")
return None
# Empty list is covered, index too high is covered, end of list
# is covered
# [(/), (a)DATA, (b)-->] [else] [<---(a)DATA, (/)]
else:
#should be just like detach_node:
head = self.begin
count = 0
link = None
plink = None
nlink = None
while head:
if index == count:
self.attach_node(head, obj)
self._length += 1
break
else:
head = head.next
count += 1
############## attach node ########################
def attach_node(self, node, obj):
# newnode
### node ### [<---a , x , b--->] ### node ###
# old previous ((a)) index node being replaced((b))
# [ ~~ , a , --->] ((x)) [<----, b , ~~ ]
newnode = DLLNode(None , obj, None)
#1 [<---a--, x , (/)] set prev of newnode
newnode.prev = node.prev
#2 [<---a--, x , --b--->] set next of newnode
newnode.next = node
#3 [~~ , a , ---x-->] set next of previous node to newnode
node.prev.next = newnode
#4 [<--x---, b , ~~ ] set previous of the index, given node to newnode
node.prev = newnode
# doing (3 and 4) out of order will break your list.
############ END attach node ################
################ prefix #####################################
############ like push, but at the beginning of the list ####
def prefix(self, obj):
# insert at the beginning of list.
head = self.begin
tail = self.end
if head == None:
print(" .... pushing....")
self.push(obj)
elif head !=None and tail == None:
# [(/), (a)DATA, (/)] None
#[(/), (b)newData, a--->][<---(b), (a)DATA, (/)]
self.end = self.begin
newnode = DLLNode(None, obj, self.end)
self.end.prev = newnode
self.begin = newnode
self._length += 1
else:
# link begin
#[(/), (a)DATA, (x)--->][<---(a), DATA(x), (/)--->]
# here link new here
#[(/), (new), (a)--->][<--(new), (a)DATA, (x)--->]...>
link = self.begin
newnode = DLLNode(None, obj, link)
self.begin.prev = newnode
self.begin = newnode
self._length += 1
def last(self):
node = self.end
if node:
return node.value
else:
return None
def first(self):
node = self.begin
if node:
return node.value
else:
return None
Code block for the pytest file:
-- pytest code block--
from ex19DLList import*
def test_push():
#colors is a placeholder for the instance DLList Double linked list
# I'm totally coping the test from single linked list and modifing it.
colors = DLList()
#Use colors placeholder get the DLL instance assigned to it
# and use it's push(function) ... The arg , obj, being "Pthalo Blue"
colors.push("Pthalo Blue")
colors._invariant()
# assert that the instances, count function returns a 1
assert colors.count() == 1
colors.push("Ultramarine Blue")
colors._invariant()
assert colors.count() == 2
colors.push("Yellow")
colors._invariant()
assert colors.count() == 3
### deciding how Zed wants this _invariant thing done.... ####
def test_pop():
## remove the last item in the linked list
colors = DLList()
colors.push("Magenta")
colors.push("Alizarin")
colors.push("yellow")
assert colors.pop() == "yellow"
colors._invariant()
assert colors.get(3) == None
colors._invariant()
assert colors.get(2) == None
assert colors.get(0) == "Magenta"
colors._invariant()
assert colors.get(1) == "Alizarin"
assert colors.pop() == "Alizarin"
colors._invariant()
assert colors.get(2) == None
assert colors.get(0) == "Magenta"
assert colors.pop() == "Magenta"
colors._invariant()
assert colors.pop() == None
assert colors.get(0) == None
colors._invariant()
#print(zero)
def test_inv_get():
# I think this is what he means by an invariant....
colors = DLList()
colors.push("Magenta")
colors.push("Alizarin")
colors.push("yellow")
assert colors.pop() == "yellow"
colors._invariant()
# get doesn't change anything... I don't think I need to do invariant check...
assert colors._get(3) == None
assert colors._get(2) == None
assert colors._get(0) == "Magenta"
assert colors._get(1) == "Alizarin"
assert colors.pop() == "Alizarin"
assert colors._get(2) == None
assert colors._get(0) == "Magenta"
assert colors.pop() == "Magenta"
assert colors.pop() == None
assert colors._get(0) == None
def test_remove():
colors = DLList()
colors.push("blue")
colors.push("yellow")
colors.remove('yellow')
colors._invariant()
colors.push("green")
colors.push("orange")
colors.push("Trillium")
colors.remove("green")
assert colors.count() == 3
assert colors.get(1) == "orange"
assert colors.remove(9) == None
assert colors.remove('blue') == 'blue'
colors._invariant()
assert colors.count() == 2
assert colors.get(0) == "orange"
assert colors.get(1) == "Trillium"
assert colors.get(2) == None
#colors.insert("umber", 1)
#assert colors.get(1) == "umber"
colors.remove('orange')
assert colors.count() == 1
def test_prefix():
colors = DLList()
#Use colors placeholder get the DLL instance assigned to it
# and use it's push(function) ... The arg , obj, being "Pthalo Blue"
colors.prefix("Pthalo Blue")
colors._invariant()
# assert that the instances, count function returns a 1
assert colors.count() == 1
colors.prefix("Ultramarine Blue")
colors._invariant()
assert colors.count() == 2
colors.prefix("Yellow")
colors._invariant()
assert colors.count() == 3
def test_shift():
# shift, reverse pop()
# remove first item of list
colors = DLList()
colors.push("Pthalo Blue")
colors.push("Ultramarine Blue")
colors.push("Yellow")
colors.shift()
colors._invariant()
assert colors.get(0) == "Ultramarine Blue"
assert colors.get(1) == "Yellow"
colors.shift()
colors._invariant()
assert colors.get(0) == "Yellow"
colors.shift()
colors._invariant()
assert colors.get(0) == None
def test_prefix():
# add to the front of the list
colors = DLList()
colors.prefix("Pthalo Blue")
colors._invariant()
colors.prefix("Ultramarine Blue")
colors._invariant()
colors.prefix("Yellow")
colors._invariant()
assert colors.get(0) == "Yellow"
assert colors.get(1) == "Ultramarine Blue"
assert colors.get(2) == "Pthalo Blue"
def test_insert():
colors = DLList()
colors.push("blue")
assert colors.get(0) == "blue"
colors.insert("new color", 0)
colors._invariant()
assert colors.get(0) == "new color"
assert colors.get(1) == "blue"
colors.push("yellow")
assert colors.count() == 3
assert colors.get(2) == "yellow"
colors.insert("orange", 2)
colors._invariant()
assert colors.get(2) == "orange"
assert colors.get(3) == "yellow"
assert colors.count() == 4
colors.insert("green", 2)
colors._invariant()
def test_length():
spam = DLList()
spam.push("jello")
assert spam._length == 1
spam.push("lions")
assert spam._length == 2
spam.push("metabolism")
assert spam._length == 3
for i in range(0, 100):
spam.push(i)
assert spam._length == 103
spam.prefix("hush")
assert spam._length == 104
for i in range(0, 100):
spam.remove(i)
assert spam._length == 4
Comments
Post a Comment