Singly Linked List

Doubly Linked List

Code Examples - doubly linked list

#!/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")