KAIST 산업및시스템공학과 문일철_ 데이터 구조 및 분석 수업을 참고하여 작성하였습니다

ch_3_4 Linked List II

Linked List II

1. Head and Tail
   : Specialized node
        - Head : Always at the first of the list
        - Tail : Always at the last of the list
        - two corner stone showing the start and the end of the list
   : optional node
        - Linked list works okay without these
        - But, having these makes implementation very convenient

2. Search precedure in singly linked list
    : just like an array, navigating from the first to the last until hit is the only way
    : No difference in the search pattern, though you can't use index any further!!!
    : Your list implementation may include the index funtion, but isn't required in the linked list
    1) Head from list
    2) detect next node
        if next == tail : break
        if next != tail : next.object= '~~'

3. Insert procedure in singly linked list
    : you see the power of a linked list
    : you need N retrievals to insert a value in the array list
    : you need only three operations
        1) with an assumption that you have a reference to the node(pre) 
        that you want to put your new node next
        2) you store a node(next), pointed by a reference
        from node(pre)'s nodeNext member variable
        3) you change a reference from node(pre)'s
        nodeNext to node(new)
        4) you change a reference from node(new)'s nodeNext to node(new)
    : Over-written with a new reference to the new node
4. Delete procedure in singly linked list
    : the another moment that you see the power of a linked list
    : you need N retrievals to delete a value in the array list
    : you need only three operation
        1) with an assumption that you have a reference to node,(pre) that you
        want to remove the node next
        1) you retreive node(next) that is two step next from node(next)
        2) you change a reference from node(pre)'s nodeNext to node(next)
    : The node will be remeoved, becuase is no reference to node(remove)
    : Over-written with a new reference to the next node of the removed one

class Node :
    nodeNext = ''
    objValue = ''
    binHead = False
    binTail = False
    def __init__(self, objValue = '', nodeNext = '',binHead = False, binTail = False):
        self.nodeNext = nodeNext
        self.objValue = objValue
        self.binHead = binHead
        self.binTail = binTail
    def getValue(self):
        return self.objValue
    def setValue(self, objValue):
        self.objValue = objValue
    def getNext(self):
        return self.nodeNext
    def setNext(self, nodeNext):
        self.nodeNext = nodeNext
    def isHead(self):
        return self.binHead
    def isTail(self):
        return self.binTail

node1 = Node(objValue='a')
nodeTail = Node(binTail = True)
nodeHead = Node(binHead = True, nodeNext = node1)

class SinglyLinkedList:
    nodeNew = ''
    nodePrev = ''
    size = 0
    def __init__(self):     # Constructor
        self.nodeTail = Node(binTail = True)
        self.nodeHead = Node(binHead= True, nodeNext= self.nodeTail)
    def insertAt(self, objInsert, idexInsert):
        nodeNew = Node(objValue=objInsert)
        nodePrev = self.get(idexInsert - 1)
        nodeNext = nodePrev.getNext()
        nodePrev.setNext(nodeNew)   # nodePrev -> nodeNew
        nodeNew.setNext(nodeNext)   # nodeNEW -> nodeNext
        self.size = self.size + 1
    def removeAt(self, idxRemove):
        nodePrev = self.get(idxRemove -1)
        nodeRemove = nodePrev.getNext()
        nodeNext = nodeRemove.getNext()
        nodePrev.setNext(nodeNext)
        self.size= self.size -1
        return nodeRemove.getValue()
    def get(self, idxRetrieve):
        nodeReturn = self.nodeHead
        for itr in range(idxRetrieve +1):
            nodeReturn = nodeReturn.getNext()
        return nodeReturn
    def printStatus(self):
        nodeCurrent = self.nodeHead
        while nodeCurrent.getNext().isTail() ==False:
            nodeCurrent = nodeCurrent.getNext()
            print(nodeCurrent.getNext())
        print()
    def getSize(self):
        return self.size