Linked list, Stack, Queue <3-2>

<< 3주차 Lecture Note 2번째>>

• Singly Linked List

---

Singly Linked List

 

2023.10.19 - [KOOC/Linear Structure & Dynamic Programming] - Linked list, Stack, Queue <3-1>

Linked list, Stack, Queue <3-1>

이전 글에서 설명한 것처럼, array 자료구조에서 데이터의 추가/삭제는 효율적이지 못한 단점이 있다.

링크드리스트를 사용하면, 필요한 위치에 추가 공간을 만들어 데이터를 쉽게 추가/삭제 할 수 있는 장점이 있다.

 

Singly Linked List는 여러개의 '노드'로 가 연결되어 있는 형태인데,

위 그림을 보면 Object와 Next가 합쳐진 하나의 큰 박스가 하나의 노드가 된다.

 

각 노드는 해당 노드에 값을 저장하는 Object 변수와, 다음 노드로 향하는 레퍼런스를 가진 변수로 구성한다.

그림에서는 Object 변수에는 'a', 'b'가 각각 저장되어 있는 것을 볼 수 있다.

 

이 중 이전 노드에서 연결되지 않은 첫 번째 노드를 Head, 다음 노드로의 연결을 갖지 않는 노드를 Tail 노드라고 하며,

이 둘을 Special nodes라고 부른다.

 

링크드리스트를 생성하는 코딩은 Array를 생성하는 것보다 더 복잡한 것이 일반적이긴 하다..

---

1. Node Class

그래서 링크드리스트는 실제로 어떻게 구현하고 활용할까?

Array는 단순히 리스트형태로 저장하면 구현되는 것이지만, 링크드리스트는 노드 클래스를 생성해서 인스턴스로 구현한다.

 

코드를 보자.

 

class Node:
    nodeNext = None
    nodePrev = ''
    objValue = ''
    binHead = False
    binTail = False
    
    def __init__(self, objValue='', nodeNext=None, binHead = False, binTail = False):
        self.nodeNext = nodeNext # 다음 노드를 지정한다
        self.objValue = objValue # 현재 노드에 저장할 값을 지정한다
        self.binHead = binHead # True인 경우 현재 노드는 Head 노드다.
        self.binTail = binTail # True인 경우 현재 노드는 Tail 노드다.
        
    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

 

위 코드는 1개의 노드를 생성하는 코드다. get/set 메서드를 이용해 특정 값을 저장하고 다음 노드를 지정할 수 있다.

Head/Tail 노드 없이 LinkedList를 간단하게 구현하는 코드를 보자.

 

node_1 = Node(objValue = 1)
node_2 = Node(objValue = 2)
node_3 = Node(objValue = 3)

node_1.setNext(node_2)
node_2.setNext(node_3)

# node_1의 값 호출
print(node_1.getValue())

# node_2의 값 호출
print(node_1.getNext().getValue())
print(node_2.getValue())

# node_3의 값 호출
print(node_1.getNext().getNext().getValue())
print(node_2.getNext().getValue())
print(node_3.getValue())

 

코드를 실행하면 결과값은 아래와 같다.

\(\quad\)1
\(\quad\)2
\(\quad\)2
\(\quad\)3
\(\quad\)3
\(\quad\)3

 

이런식으로 하나의 노드에 값을 저장하고, 다음으로 연결하는 노드를 지정함으로써 1 2 3 이라는 리스트를 생성할 수 있다.

 

만약 1과 2 사이에 'a'가 삽입되어야 한다면, 'a' 값을 저장하는 노드(node_a)를 새로 생성해 node_1의 다음 노드로 지정하고,

node_a의 다음 노드로 node_2를 지정하면 되기때문에 데이터의 추가/삭제가 편리해지는 것이다. (이건 아랫부분에서 좀더 자세히 보자.)

---

2. Head and Tail

Head와 Taild은 LinkedList의 시작과 끝을 알려주는 노드로, Object의 값을 지정하지 않는다.

만약, 비어있는 LinkedList를 생성한다면 아래 그림과 같을 것이다.

굳이 Head / Tail 노드 없이도 링크드리스트를 구성할 수는 있지만,

Head와 Tail은 리스트의 범위를 지정해주는 역할을 하기때문에 함께 구성해주는 것이 유용할 때가 많다.

---

3. Search Procedure  in Singly Linked List

Array 구조에서 값을 searach 했던 것처럼, 링크드리스트에서도 search가 가능하다.

코드는 나중에 구현해보기로 하고, 그림을 먼저 보면 아래와 같다.

위 링크드리스트에서 'c'를 찾는 프로시저를 실행해보면 아래 절차를 따른다.

\(\quad\) 1) head node를 불러와 head/Tail 여부를 확인한다. head가 맞을 경우 다음 노드를 호출한다.

\(\quad\) 2) 호출된 노드의 Object 값이 'c'인지 확인하고, 맞으면 break, 틀리면 다음 노드를 호출한다.

\(\quad\) 3) 2번을 반복하면서 tail 노드까지 확인 후, 마지막 노드가 tail이면 프로시저를 종료한다.

 

위 절차대로 하게 되면, 링크드리스트가 N개 일 때 총 N번의 retrieval을 실행 후 프로시저가 종료된다.

만약 'c'가 아닌 'd'를 찾는다면, 'd'는 위 리스트에 존재하므로 프로시저는 'd'를 찾은 후 종료될 것이다.

---

4. Insert Procedure in Singly Linked List

Array 형태의 리스트 중간에 새로운 데이터를 추가하는 경우, retrievals는 리스트의 길이만큼 필요하므로 비효율적이라고 했다.

Linked List에서는 데이터 추가에 retrievals 낭비가 없어진다. 아래 그림을 보자.

 

 

(3. Search Procedure in Singly Linked List) 에서 본 그림의 리스트에는 'c'가 존재하지 않았다.

위 그림은 링크드리스트에 'c'를 새로 추가하는 과정을 보여주는 것으로,

\(\mathrm{Node}_{prev} \)를 node_b, \(\mathrm{Node}_{next} \)를 node_d, \(\mathrm{Node}_{new} \)를 node_c라 하자.

 

기존의 리스트에 'c'를 새로 추가하고싶으면 아래의 절차를 따른다.

\(\quad\) 1) 'c'를 Object Value로 하는 node_c를 생성한다.

\(\quad\) 2) node_b의 next에 node_c를 연결함으로써, node_d와의 연결을 끊는다. (Over-written)

\(\quad\) 3) node_c의 next로 node_d를 연결한다.

 

이렇게 하면 Array 형태처럼 새로운 빈 리스트에 모든 원소를 search하며 카피하지 않고,

3개의 Operation만으로도 데이터를 추가할 수 있어 매우 간편하며 효율적이다.

---

 

5. Delete Procedure in Singly Linked List

Insert는 추가할 노드를 새로 생성하는 반면, Delete는 그런 과정이 없어 훨씬 간편해진다.

 

(4. Insert Procedure in Singly Linked List)에서 생성한 링크드리스트를 다시 생각해보자.

만약 링크드리스트에서 'c'값을 삭제하고싶다면,

단순히 node_b의 next를 node_d로 Over-written 해주면 된다.

 

이 때, node_c는 여전히 next가 node_d를 가르키고 있지만, 어떤 레퍼런스도 node_c를 찾아갈 수 없으므로

실제로는 node_c가 삭제된 것과 동일시된다.

파이썬에는 garbage collector가 존재해서, 코드상으로 사용되지 않는 변수는 자동 삭제함으로써 메모리를 줄여준다.

---

6. Singly Linked List 구현

앞에서 개별 노드는 코드로 구현했다. 이번에는 노드 클래스를 활용한 링크드리스트 구현 코드를 보자.

class SinglyLinkedList:
    nodeHead = ''
    nodeTail = ''
    size = 0
    
    def __init__(self):
        self.nodeTail = Node(binTail=True)
        self.nodeHead = Node(binHead=True, nodeNext = self.nodeTail)
        
    def get(self, idxRetrieve):
        """ 지정한 인덱스에 해당하는 노드 반환 """
        nodeReturn = self.nodeHead
        for itr in range(idxRetrieve + 1):
            nodeReturn = nodeReturn.getNext()
        
        return nodeReturn
        
    def insertAt(self, objInsert, idxInsert):
        """ 링크드리스트의 특정 인덱스에 새로운 값 추가 """
        # 삽입할 노드 생성
        nodeNew = Node(objValue = objInsert)
        
        # 추가될 노드의 이전 노드 지정
        nodePrev = self.get(idxInsert - 1)
        
        # 추가될 노드의 다음 노드 지정
        nodeNext = nodePrev.getNext()
        
        # 이전 노드 -> 새로운 노드 -> 다음 노드 연결
        nodePrev.setNext(nodeNew)
        nodeNew.setNext(nodeNext)
        
        # 노드가 추가된 만큼 링크드리스트의 사이즈 증가
        self.size += 1
        
    def deleteAt(self, idxDelete):
        """ 링크드리스트의 특정 인덱스에 해당하는 노드 제거 """
        
        # 삭제할 노드의 이전 노드 지정
        nodePrev = self.get(idxDelete - 1)
        
        # 삭제할 노드 지정
        nodeDelete = nodePrev.getNext()
        
        # 노드 삭제 후 이전 노드에 연결할 노드 지정(삭제 노드의 다음 노드)
        nodeNext = nodeDelete.getNext()
        
        # 삭제 대상의 이전 노드와 다음 노드 연결
        nodePrev.setNext(nodeNext)
        
        # 노드 삭제된 만큼 링크드리스트의 사이즈 감소
        self.size -= 1
        
        return nodeDelete.getValue()
    
    def printStatus(self):
        """ 현재 리스트의 Head 다음 노드부터 Tail 이전 노드까지의 값 순서대로 출력 """
        nodeCurrent = self.nodeHead
        while nodeCurrent.getNext().isTail() == False:
            nodeCurrent = nodeCurrent.getNext()
            print(nodeCurrent.getValue(), end=" ")
        print('\n')

구현한 SinglyLinkedList 클래스는 초기값으로 Head와 Tail을 갖는 텅 빈 리스트이며,

insertAt과 deleteAt 메서드로 리스트에 값을 추가 또는 삭제할 수 있다.

 

리스트 값을 추가/삭제한 코드는 아래와 같다.

singlylinkedlist = SinglyLinkedList()

singlylinkedlist.insertAt('a', 0)
singlylinkedlist.insertAt('b', 1)
singlylinkedlist.insertAt('c', 2)
singlylinkedlist.insertAt('d', 3)
singlylinkedlist.insertAt('e', 4)
singlylinkedlist.printStatus()

singlylinkedlist.deleteAt(1)
singlylinkedlist.deleteAt(3)
singlylinkedlist.printStatus()

값을 추가/삭제하고 printStatus 메서드로 리스트의 상태를 출력해보면 결과는 아래와 같다.

 

\(\quad \)a b c d e 

\(\quad \)a c d 

0 ~ 4 인덱스에 'a' ~ 'e'가 추가 되었을 때의 리스트 상태와,

1번째, 3번째 인덱스의 노드를 삭제한 후의 리스트 상태를 볼 수 있다.

 

링크드리스트 구현 자체는 코드가 조금 길긴 하지만, 원리를 이해하면 쉽게 작성 가능한 수준인 것 같고,

대용량 데이터 처리에서 꽤나 유용하게 사용할 수 있을 것 같다.