파이썬[Python] 037 linked list 생성 및 활용

이번 포스팅은 데이터 구조에서 매우 많이 사용되는 linked list입니다. 매우 많은 사람들이 c언어에서 linked list를 매우 많이 사용했습니다. 그래서 c언어를 하다가 python에 오면 다음과 같은 부분들에 대해서 생성하고자 합니다. 

 

그래서 오늘은 linked list 생성하는 방법 및 활용하는 방법에 대해서 살펴 보겠습니다. 

먼저, 생성하기에 앞서 linked list에 대해서 간단하게 살펴 보겠습니다. 

linked list는 가장 크게 Node들로 구성이 됩니다.Node는 노드가 가지는 값과 다음 노드가 어떻 녀석인지에 대한 부분(Next)으로 나누어지고 관련된 부분에 대해서 인지 해야 합니다. 그리고 리스트의 가장 마지막 녀석의 Next는 Null값입니다. 

 

그리고 또한 head라는 부분이 존재합니다. 이 head는 linked list를 접속하기 위한 유일한 접근 공간 이라고 생각하시면 됩니다. 

 

그럼 한번 생성해보도록 하겠습니다. 

 

생성 

class Node:
    def __init__(self, value):
        self.val = value
        self.next = None

class SLinkedList:
    def __init__(self):
        self.head = None

LList = SLinkedList()
LList.head = Node("LNode1")
Node2 = Node("LNode2")
Node3 = Node("LNode3")
LList.head.next = Node2
Node2.next = Node3

최초에 LNode1 이라는 부분을 head로 초기화 합니다. 그리고 Node2, Node3을 각각 생성하고 next를 통해서 각 맴버들을 연결했습니다. 

 

맴버 추가 

1. 가장 처음에 추가 하기 

다음 그림과 같이 새로운 노드를 추가하고 Next를 기존 head가 가리키고 있는 부분으로 지칭합니다. 그런 후 Head가 가르키고 있는 부분을 새로 생성한 부분으로 놓습니다. 

그럼 위의 부분을 코드로 생성해 보겠습니다. 

class Node:
    def __init__(self, value):
        self.val = value
        self.next = None

class SLinkedList:
    def __init__(self):
        self.head = None

    def mprint(self):
        printval = self.head
        while printval is not None:
            print(printval.val)
            printval = printval.next

    def AddFirst(self, nvalue):
        addedNode = Node(nvalue)
        addedNode.next = self.head
        self.head = addedNode

LList = SLinkedList()
LList.head = Node("LNode1")
Node2 = Node("LNode2")
Node3 = Node("LNode3")
LList.head.next = Node2
Node2.next = Node3
LList.AddFirst("LNode4")
LList.mprint()

위의 부분을 실행하면 다음과 같은 예제가 나옵니다. ( 맴버들의 추가 부분을 확인하기 위해서 별도로 mprint 함수를 추가하였습니다. )

LNode4
LNode1
LNode2
LNode3

 

2. 가장 마지막에 추가 하기 

 

일단 먼저 가장 마지막 맴버를 찾아서, 그 녀석의 Next를 새로 생성한 부분을 맵핑해주시면 됩니다. 

코드로 살펴보겠습니다. 

class Node:
    def __init__(self, value):
        self.val = value
        self.next = None

class SLinkedList:
    def __init__(self):
        self.head = None

    def mprint(self):
        printval = self.head
        while printval is not None:
            print(printval.val)
            printval = printval.next

    def AddLast(self, nvalue):
        LListM = self.head
        while (LListM.next):
            LListM = LListM.next
        addedNode = Node(nvalue)
        LListM.next = addedNode


LList = SLinkedList()
LList.head = Node("LNode1")
Node2 = Node("LNode2")
Node3 = Node("LNode3")
LList.head.next = Node2
Node2.next = Node3
LList.AddLast("LNode5")
LList.mprint()

While(LListM.next) 는 LListM.next가 None이 될때까지 반복함으로 가장 마지막 맴버를 확인할 수 있습니다. 위의 코드를 실행하면 다음과 같은 결과가 나옵니다. 

LNode1
LNode2
LNode3
LNode5

 

삭제 하기 

삭제하기는 몇가지 부분을 확인해야 합니다. 첫번째 맴버인지에 대해서 확인해야하고, 만약 첫번째 맴버이면 next를 head에 연결시켜야 합니다. 그런 후 Head가 가르키던 값은 삭제하면됩니다. 

 

만약 중간에 있는 녀석이면, List를 반복하면서 녀석을 찾습니다. 하지만 반복하던 중에 지나간 녀석에 대한 정보도 다른 변수로 저장해두고, next를 비교 대상값으로 반환합니다. 만약 비교 대상 값을 찾으면 그의 next 를 앞서 저장한 정보의 next로 연결하고 비교대상자를 삭제하면 됩니다. 

 

다음 코드로 살펴보겠습니다. 

class Node:
    def __init__(self, value):
        self.val = value
        self.next = None

class SLinkedList:
    def __init__(self):
        self.head = None

    def mprint(self):
        printval = self.head
        while printval is not None:
            print(printval.val)
            printval = printval.next

    def RemoveNode(self, Rdata):
	    HeadVal = self.head
	    if (HeadVal is not None):
            if (HeadVal.val == Rdata):
                self.head = HeadVal.next
                HeadVal = None
                return
        while (HeadVal is not None):
            if HeadVal.val == Rdata:
                break
            prev = HeadVal
            HeadVal = HeadVal.next
        if (HeadVal == None):
            return
        prev.next = HeadVal.next
        HeadVal = None

LList = SLinkedList()
LList.head = Node("LNode1")
Node2 = Node("LNode2")
Node3 = Node("LNode3")
LList.head.next = Node2
Node2.next = Node3
LList.RemoveNode("LNode2")
LList.mprint()

위의 코드를 실행하면 다음과 같은 결과값이 나옵니다. 

LNode1
LNode3

 

오늘은 파이썬[python]으로 Linked List를 생성하고 활용하는 방법에 대해서 살펴봤습니다. 많은 분들이 이와 같은 부분을 적극 활용합니다. 저 또한  Autosar 관련 작업을 할때 다음과 같은 부분들을 활용했었던 기억이 납니다. 

혹 궁금하신점이나 문의 사항 있으시면 언제든지 댓글 및 방명록에 글 남겨주시길 바랍니다.