#!/usr/bin/python3
# ==================================================================
# doubly linked list
# ==================================================================
#
# (list head) (list node) (list node) (list node)
# +-------+ +-------+ +-------+ +-------+
# | first |---->| flink |---->| flink |---->| None |<--+
# +-------+ +-------+ +-------+ +-------+ |
# | last |--+ | None |<----| blink |<----| blink | |
# +-------+ | +-------+ +-------+ +-------+ |
# | |
# +------------------------------------------+
#
# flink - forward link (sometimes call next link).
# blink - backward link (sometimes called previous link).
# first - link to first element in the list.
# last - link to last element in the list.
#
# ==================================================================
# ------------------------------------------------------------------
# define list node (element) class
# ------------------------------------------------------------------
class Node:
def __init__(self,initdata):
self.data = initdata
self.flink = None
self.blink = None
return
def getData(self):
return self.data
def setData(self,newdata):
self.data = newdata
return
def getFlink(self):
return self.flink
def getBlink(self):
return self.blink
def setFlink(self,newflink):
self.flink = newflink
return
def setBlink(self,newblink):
self.blink = newblink
return
def setFlinkBlink(self,newflink,newblink):
self.flink = newflink
self.blink = newblink
return
# ------------------------------------------------------------------
# define list head class
# ------------------------------------------------------------------
class LinkedList:
def __init__(self):
self.first = None
self.last = None
return
def addHeadOfList(self,newnode):
newnode.setFlinkBlink(self.first,None)
if self.first == None:
self.first = newnode
self.last = newnode
return
temp = self.first
temp.setBlink(newnode)
newnode.setFlink(temp)
self.first = newnode
return
def addTailOfList(self,newnode):
newnode.setFlinkBlink(None,self.last)
if self.last == None:
self.last = newnode
self.first = newnode
return
temp = self.last
temp.setFlink(newnode)
newnode.setBlink(temp)
self.last = newnode
return
def addAfterNode(self,listnode,newnode):
temp = listnode.getFlink()
if temp == None:
self.addTailOfList(newnode)
return
temp.setBlink(newnode)
newnode.setBlink(listnode)
newnode.setFlink(temp)
listnode.setFlink(newnode)
return
def addBeforeNode(self,listnode,newnode):
temp = listnode.getBlink()
if temp == None:
self.addHeadOfList(newnode)
return
temp.setFlink(newnode)
newnode.setFlink(listnode)
newnode.setBlink(temp)
listnode.setBlink(newnode)
return
def removeNode(self,listnode):
temp1 = listnode.getFlink()
temp2 = listnode.getBlink()
if temp1 == None and temp2 == None: # listnode is only node in list?
self.first = None
self.last = None
elif temp2 == None: # listnode first node in list?
temp1.setBlink(None)
self.first = temp1
elif temp1 == None: # listnode last node in list?
temp2.setFlink(None)
self.last = temp2
else: # listnode somewhere in the list
temp1.setBlink(temp2)
temp2.setFlink(temp1)
listnode.setFlink(None) # belt and suspenders
listnode.setBlink(None)
return
def isEmpty(self):
if self.first == None:
return True
else:
return False
def size(self):
current = self.first
count = 0
while current != None:
count = count + 1
current = current.getFlink()
return count
def LocateNodeData(self,data):
temp = self.first
while temp != None:
if data == temp.getData():
return temp
temp = temp.getFlink()
return None
def getFirstNode(self):
return self.first
def getLastNode(self):
return self.last
def clearlist(self):
c = 0
temp = self.getFirstNode()
while temp != None:
tmp = temp.getFlink()
temp.setFlink(None)
temp.setBlink(None)
c += 1
temp = tmp
self.first = None
self.last = None
return c
# ------------------------------------------------------------------
# main (for testing)
# ------------------------------------------------------------------
if __name__ == "__main__":
def printListForward(list,label):
print("-- linked list ----------------------")
if label != None:
print(label)
if list.isEmpty():
print("List is Empty")
else:
temp = list.getFirstNode()
while temp != None:
print(f" {temp.getData()}")
temp = temp.getFlink()
print("-- end list -------------------------")
return
def printListBackward(list,label):
print("-- linked list ----------------------")
if label != None:
print(label)
if list.isEmpty():
print("List is Empty")
else:
temp = list.getLastNode()
while temp != None:
print(f" {temp.getData()}")
temp = temp.getBlink()
print("-- end list -------------------------")
return
def printNode(node,label):
print("-- node -----------------------------")
if label != None:
print(label)
if node == None:
print("node is None")
else:
print(f"data {node.getData()}")
if node.flink == None:
print("flink None")
else:
print(f"flink {node.flink.getData()}")
if node.blink == None:
print("blink None")
else:
print(f"blink {node.blink.getData()}")
print("-------------------------------------")
return
def printListHead(list):
print("-- list head-------------------------")
if list.first == None:
print("first None")
else:
print(f"first {list.first.getData()}")
if list.last == None:
print("last None")
else:
print(f"last {list.last.getData()}")
print("-------------------------------------")
return
# -- insert nodes at the start of a list
mylist1 = LinkedList()
mylist1.addHeadOfList(Node(31))
mylist1.addHeadOfList(Node(77))
mylist1.addHeadOfList(Node(17))
node17 = mylist1.getFirstNode() # save node 17 for later
mylist1.addHeadOfList(Node(93))
mylist1.addHeadOfList(Node(26))
mylist1.addHeadOfList(Node(54))
# -- insert nodes at the end of a list
mylist2 = LinkedList()
mylist2.addTailOfList(Node(131))
node131 = mylist2.getFirstNode() # save node 131 for later
mylist2.addTailOfList(Node(177))
mylist2.addTailOfList(Node(117))
node117 = mylist2.getFirstNode() # save node 117 for later
mylist2.addTailOfList(Node(193))
mylist2.addTailOfList(Node(126))
mylist2.addTailOfList(Node(154))
node154 = mylist2.getLastNode() # save node 154 for later
# -- print the size of the lists
print(f"list 1 size is {mylist1.size()}")
print(f"list 2 size is {mylist2.size()}")
# -- print the lists (forwards and backwards)
printListForward(mylist1,"forward list 1")
printListBackward(mylist1,"backward list 1")
printListForward(mylist2,"forward list 2")
printListBackward(mylist2,"backward list 2")
# -- insert nodes into list 1 before and after node (17)
node100 = Node(100)
node200 = Node(200)
mylist1.addBeforeNode(node17,node100)
mylist1.addAfterNode(node17,node200)
printListForward(mylist1,"inserted nodes into list 1 - list forward")
printListBackward(mylist1,"inserted nodes into list 1 - list backward")
# -- insert at the start and end of list 2
node300 = Node(300)
node400 = Node(400)
mylist2.addBeforeNode(node131,node300)
mylist2.addAfterNode(node154,node400)
printListForward(mylist2,"inserted nodes into list 2 - list forward")
printListBackward(mylist2,"inserted nodes into list 2 - list backward")
# -- test removing nodes
mylist1.removeNode(node100)
mylist1.removeNode(node200)
printListForward(mylist1,"remove nodes into list 1 - list forward")
printListBackward(mylist1,"remove nodes into list 1 - list backward")
mylist2.removeNode(node300)
mylist2.removeNode(node400)
printListForward(mylist2,"remove nodes into list 2 - list forward")
printListBackward(mylist2,"remove nodes into list 2 - list backward")
# -- locate data in the list?
v = 54
n = mylist1.LocateNodeData(v)
if n == None:
print("did not fine {v} in the list")
else:
print(f"found {v} in the list")
v = 99
n = mylist1.LocateNodeData(v)
if n == None:
print(f"did not fine {v} in the list")
else:
print(f"found {v} in the list")