[선형 자료구조 - Python] 연결 리스트(Linked List)

사실 Python에서 Linked List를 잘 사용하지 않는 것같다. 왜냐하면 구현이 편한, list나 deque로 어느정도 커버가 가능하기 때문이다. 하지만 반드시 필요한 자료구조이기 때문에, 이번 기회에 이해해 보도록 하자. 일반적인 자료구조에서의 리스트란, 순서를 가진 데이터의 집합을 가리키는 추상 자료형(abstract data type)이다. 자료구조의 관점에서 리스트의 종류로는, 순차 리스트와 연결 리스트로 나뉜다. 오늘 다루고자 하는 내용은 리스트의 한 종류인, 연결 리스트(Linked List)에 대해 알아보자.

 

• 순차 리스트: 저장소를 배열형태로 만드는 것. 연속적인 메모리 공간에 저장(python에서 list)
• 연결 리스트: 저장 할때 마다 메모리를 확보해서 추가시키는 것. 메모리의 동적할당을 기반으로 구현

 

---

 

 

연결 리스트는 이름에서 알 수 있듯, 각각의 데이터들이 순서대로 연결되어 있는 리스트 이다. 아래의 그림을 보면, A에서 D 까지 순차적으로 화살표를 가지고 연결되어 있는 것을 알 수 있다.  아래 그램을 보면, 삭제 추가 시 끊어진 부분을 다시 연결만 하면 되는 것을 확인 할 수 있다.

hanpy

hanpy

hanpy

hanpy

hanpy

 

 

 

화살표 방향으로 연결되어 있기 때문에, 건너뛰거나 화살표 반대방향으로 자료조회는 불가능하다. (물론 양방향 연결리스트는 가능하지만, 여기서는 단방향만 확인하도록 하자.) 즉, 순차리스트와 다르게 원하는 인덱스 위치를 바로 찾아갈 수 없고 첫 노드부터 화살표를 따라 순차적으로 확인을 하면서 찾아야한다. 기본적인 용어 설명은 아래와 같다.

• 각각의 element(A, B, C 등등)를 node라고 한다.
• 가장 앞의 노드의 이름이 head node이다.
• 가장 뒤의 노드의 이름은 tail node이다.
• 각 노드는 데이터와 뒤쪽 노드를 가리키는 pointer를 가진다.
• 특정 노드 기준으로 이전 노드를 predecessor node라 하고 뒤쪽 노드를 successor node라고 한다.

---

연결리스트(Linked List) 특징

연결리스트는 인덱스 위치로 바로 찾아갈 수 없고, 개별적으로 위치하고 있는 원소의 주소를 연결하여 하나의 전체적인 자료구조를 이룬다. 따라서 연결리스트는 링크를 통해 원소에 접근하므로, 순차 리스트에서처럼 물리적인 순서를 맞추기 위한 작업이 필요하다고 할 수 있다. 이러한 연결리스트는 자료구조의 크리를 동적으로 조정 가능하여 메모리를  효율적으로 사용이 가능하다(새로운 데이터 추가 시 메모리 할당하 사용한다). 효율적인 메모리 사용은 무슨 말일까? 우선은 메모리에 대해 좀 더 알아보자.

 

순차 리스트와 연결리스트의 메모리 사용 차이점

파이썬의 모든 자료는 객체로 저장되고, 객체의 주소를 저장할 때 연속적인 메모리 공간에 저장이 된다. 아래의 예를 보자.

 

# id() 함수를 사용하면, 식별가능한 유일한 값이 뜬다.
a = 100
b = 100
print(id(a), id(b))

```
1994862384 1994862384
```

 

위의 코드의 결과로 알 수 있는 것은, a와 b가 같은 값을 가리키고 있다는 것이다. 그리고 파이썬 자체는 100이라는 값을 저장할 메모리를 하나만 만든 다는 것을 알 수 있다. 아래는 배열에 들어 있는 메모리 주소 값을 print하는 예시이다.

 

arr = [0]*5
for i in range(5):
    print(id(arr[i]))
    
```
1994859184
1994859184
1994859184
1994859184
1994859184
```

 

위의 코드로 알 수 있는 것은 id가 다 같다는 말은 arr 안에 있는 인덱스의 데이터 값들이 모두 같은 값을 가리키고 있다는 것을 알 수 있다. 배열의 값 하나를 다른 값을 넣어서 확인을 해보자.

 

arr = [0]*5
arr[3] = 1
for i in range(5):
    print(id(arr[i]))
    
```
1994859184
1994859184
1994859184
1994859216
1994859184
```

 

위의 값을 통해 파이썬은 연속적인 메모리공간에 객체를 가리키는 주소만 적혀있다는 것을 알 수 있다. 그렇다면 연속적인 메모리공간의 크기는 어떻게 될까? 아래의 코드를 확인해 보자.

 

import sys
arr = []
size = sys.getsizeof(arr)
print(size)    # 실제 가리키는 객체 없다
for i in range(1000):
    arr.append(None)
    new_size = sys.getsizeof(arr)
    if size != new_size:
        print(size, new_size)
        size = new_size
```
56
56 88
88 120
120 184
184 248
248 312
312 376
376 472
472 568
568 664
664 792
792 920
920 1080
1080 1240
...
...
```

 

배열 내부에 가리키는 값이 없더라도, 크기가 증가함에 따라 메모리가 커지는 것을 알 수 있다. 파이썬에서 위와 같은 불필요한 메모리가 사용되는 경우가 있다면, 배열보다는 연결 리스트를 사용하는 것이 현명하다는 것을 알 수 있다.

 

---

연결 리스트(Linked list) 기본구조

파이썬에서 연결 리스트에 데이터를 저장하기 위해, class로 정의된 Node를 쓴다.

 

Node란

연결 리스트의 구조는 다음과 같다. 하나의 Node에는 data 필드와 link 필드를 가진다. data 필드는 실제 데이터를 저장하는 자료구조로, 저장할 원소의 종류나 크기에 따라 구조를 정의하여 사용한다. link 필드는 다음 Node의 주소를 저장하는 자료구조이다. 이러한 data 필드와 link 필드는 묶어서 class로 Node를 만든다.

 

Head란

첫번째 노드의 객체에 해당하는 것을 찾아 갈 수 있도록 주소를 저장할 Head가 필요하다.

 

연결 구조

• 16진수로 나타내는 값이 주소이다.( ex) 0x1018 )
• 각 노드마다 다음 노드의 주소(link 필드)에 의해 다음 노드와 연결되는 구조를 가진다.
• head가 가장 앞의 노드를 가리키고, link 필드가 연속적으로 다음 노드를 가리키다.
• 마지막 노드는 다음으로 오는 노드가 없다고 반드시 나타내야한다. 이러한 의미로, 파이썬에서는 None을 마지막에 저장해 둔다. 안 하면 오류가 발생한다. (C 언어 에서는 NULL을 적어준다.)

 

---

단일(단순) 연결 리스트 구현하기

연결리스트를 구현하려면 각 Node에 대한 클래스가 따로 필요하다. Node class 코드를 먼저 확인하자.

 

Node class 만들기

class Node:
    def __init__(self, d=0, n=None):
        self.data = 0
        self.next = None
        print(d, '생성')

    def __del__(self):
        print(self.data, '삭제')

arr = []
for i in range(5):
    arr.append(Node(i))
print(arr)

```
0 생성
1 생성
2 생성
3 생성
4 생성
[<__main__.Node at 0x7f0db06db370>,
 <__main__.Node at 0x7f0db13e1150>,
 <__main__.Node at 0x7f0db06da500>,
 <__main__.Node at 0x7f0db06da650>,
 <__main__.Node at 0x7f0db06db2b0>]
```

 

__repr__() 메소드를 정의하지 않았기 때문에 기본적으로 클래스 이름과 객체 주소를 반환한다.

 

Node 클래스는 2개의 필드(data, next)로 구성이 된다. data는 data에 대한 참조값을 의미하고, next는 뒤쪽 노드에 대한 참조 데이터를 담고 있다. __init__에서는 data를 받아서 data와 next필드를 추가한다. 전달받은 인수가 없다면 None으로 생성한다. __del__() 메서드는 소면자 메서드로 생성자와 반대로 인스턴스를 삭제 할 떄 자동으로 호출된다. 삭제 시 필요한 로직이 있다면 이곳에 적어주면 된다.

 

 

LinkedList 만들기

class Node:
    def __init__(self, d=0, n=None): # 생성자
        self.data = d        # 정수 값 저장
        self.next = n        # 다음 노드 주소

class LinkedList:
    def __init__(self):
        self.head = None # 첫 번째 노드
        self.size = 0     # 노드의 수

my_list = LinkedList()

def printList(lst): # lst는 LinkedList 객체 주소를 받는거다.
    cur = lst.head
    print('cur.data : ', cur.data)

    while cur is not None:
        print('data : ', cur.data)
        print('next : ', cur.next)
        cur = cur.next

n5 = Node(5);
n4 = Node(4, n5)  # 노드는 4번이고 n5를 가르켜라.
n3 = Node(3, n4)
n2 = Node(2, n3)
n1 = Node(1, n2)
my_list.head = n1    # mylist의 head가 n1이라고 지정
my_list.size = 5

print(my_list) # <__main__.LinkedList object at 0x7f0db06d97e0>
printList(my_list)
```
cur.data :  1
data :  1
next :  <__main__.Node object at 0x7f0db071cd30>
data :  2
next :  <__main__.Node object at 0x7f0db071f0d0>
data :  3
next :  <__main__.Node object at 0x7f0db071cca0>
data :  4
next :  <__main__.Node object at 0x7f0db071eb60>
data :  5
next :  None
```

 

위의 코드를 살펴보면, Node들이 n1 > n2 > n3 > n4 > n5로 연결되어 있는 것을 알 수 있다. 구현을 해보면 확실히 단점은 순차 접근을 해야하기 때문에 마지막 노드까지 가려면, 처음부터 하나씩 접근을 해야한다.

 

 

 

LinkedList CRUD 만들기

class Node:
    def __init__(self, d=0, n=None): # 생성자
        self.data = d        # 정수 값 저장
        self.next = n        # 다음 노드 주소

class LinkedList:
    def __init__(self):
        self.head = None # 첫 번째 노드
        self.tail = None # 마지막 노드
        self.size = 0     # 노드의 수를 알 수 있도록 적어둠

mylist = LinkedList()

def printList(lst): # lst는 LinkedList의 출발 객체 주소를 받는거다.
    if lst.head is None:    # 빈리스트인 경우 주의
        return        #빈리스트인지 체크
    cur = lst.head    #첫번째 노드 복사

    while cur is not None:
        print(cur.data)
        cur = cur.next  # 모든 노드를 순서대로 가져올 수 있다

def insertLast(lst, new): # new는 새로 추가할 노드 객체
    # 빈리스트 처리
    if lst.head is None:
        lst.head = lst.tail = new # 비어있으니 처음과 끝이 같다
    else:
        # 빈리스트 아니면 마지막 노드를 찾으면 된다.
        lst.tail.next = new
        lst.tail = new    # 새로 추가되는걸 마지막으로 함.
    lst.size += 1

def deleteLast(lst):
    if lst.head is None:
        return
    pre, cur = None, lst.head
    while cur.next is not None:
        pre = cur    # pre가 cur를 따라간다.
        cur = cur.next
    if pre is None: # 노드가 하나인 경우
        lst.head = lst.tail = None
    else: # 노드가 여러개인 경우
        pre.next = None
        lst.tail = pre
    lst.size -= 1


def insertFirst(lst, new): # new의 next을 head가 가리키는걸로 넣고 head를 new로 가리키게 하면된다.
    if lst.head is None:
        lst.head = lst.tail = new
    else:
        new.next = lst.head
        lst.head = new
    lst.size += 1

def deleteFirst(lst): # 노드가 한개일 경우를 주의하자
    if lst.head is None:
        return
    lst.head = lst.head.next
    if lst.head is None: # 한개인 경우
        lst.tail = None

def insertAt(lst, idx, new):
    # 빈리스트일 경우, idx == 0
    if lst.head is None or idx == 0:
        insertFirst(lst, new)
    # 마지막 추가하는 경우 idx >= lst.size
    elif idx >= lst.size:
        insertLast(lst, new)
    # 중간에 추가하는 경우(head, tail이 바뀔리 없다.)
    else:
        pre, cur = None, lst.head
        for _ in range(idx):
            pre = cur
            cur = cur.next

        new.next = cur
        pre.next = new
        lst.size += 1

#def deleteAt(lst, idx): # 빈리스트 처리해. 그리고 처음, 중간 마지막 나눠서 구분해서 구현하자.        

for i in range(5):
    insertLast(mylist, Node(i))
    printList(mylist)

while mylist.size:    
    # 마지막 노드 삭제 하려면 마지막 앞에 노드를 None으로 바꾸고 tail도 마지막 앞으로 옮겨야한다.
    # 그런데 단일 연결 리스트는 마지막 노드를 안다고 마지막 앞의 노드를 알 수 없다. 그래서 처음부터 다시 찾아야한다. 이런경우는 이중연결리스트 쓰는게 좋다.찾기전에 빈리스트 체크 부터 당연히 해야한다.
    deleteLast(mylist)
    printList(mylist)

 

 

코드를 하나씩 보면 크게 어려운 부분은 없다. 주의할 점으로는 마지막 노드 삭제 시, 마지막 앞의 노드를 None로 변경하고 tail도 마지막 앞으로 옮겨준다. 이러한 구조기 때문에 마지막 노드를 알고 있다고 해도, 마지막 앞의 노드를 알 수 없다. 따라서 검색 시 처음부터 다시 찾아야 한다. 이러한 검색이 자주 일어나야 한다면, 이중 연결 리스트를 사용하는 것이 좋다. 

 

이중 연결 리스트의 구현법도 사실 간단하다. 우리는 위의 단일 연결리스트에서는 Node에  next로 다음 Node값을 넣어준다. 이중 연결 리스트에서는 next에서 추가로 pre 까지 넣어서 이전 Node의 정보도 넣어주기만 하면 된다. 한번 구현해 보면 좋을 것 같다.