[자료구조와 알고리즘 | 파이썬] Linked List(연결 리스트) | Singly linked list(단일 연결 리스트)와 Doubly linked list(이중 연결 리스트)

1. Linked List ADTs

Linked List를 ADT(Abstract Data Types)로 만들어 볼 것입니다.

참고로 파이썬의 리스트라고 하는 자료구조는 링크드리스트입니다!

 

그래서 생각해 보시면 다른 언어와 달리 파이썬에서 리스트(다른 언어의 배열)를 선언할 때는 그 크기를 지정하지 않고도 원소를 삽입하는 것을 아실 수 있습니다. 그래서 다른 언어의 배열에서 특정 인덱스에 접근하는 것은 random access이기 때문에 시간 복잡도가 O(1)이지만 파이썬에서는 노드를 타고 쭉 가기 때문에 O(N)의 시간복잡도를 갖습니다.

 

그렇다면 이제 링크드리스트에 대해서 알아볼까요?

 

2. Singly linked lists (단일 연결 리스트)

중요한 컨셉

• head node: 리스트에서 가장 앞에 있는 노드를 말하고 그 노드를 가리키는 포인터로 head라는 변수가 존재하는 것이다.
  • head 변수가 가리키고 있는 노드가 head!

 

singly linked list는 두 연속적인 node들 사이에 하나의 pointer만을 가진 리스트를 말합니다. 또한 single이라는 단어에서 알 수 있듯이 단방향으로만 이동될 수 있습니다.

 

그래서 다음과 같은 특성들을 갖습니다.

• 한 노드가 다른 노드를 가리킴
• 각 노드마다 데이터가 들어있음
• 포인터는 다음 노드를 가리킴

 

즉, 리스트의 첫 번째 node에서부터 마지막 node로 갈 수 있지만 last node에서 first node로 갈 수는 없는 것입니다.

Singly linekd list ADT는 다음 연산을 포함합니다:

• insert()
• delete()
• traverse()

우리가 Linked List를 ADT로 만들면 위와 같은 함수를 사용하여 데이터 관리를 굉장히 용이하게 할 수 있게 됩니다.

 

3. Array(배열) vs. Linked List(연결 리스트)

Array(배열)의 특징

• read, write이 빠르다.(O(1))
  • index가 있기 때문에 random access가 가능하기 때문 (인덱스로 바로 접근하기 때문)
• insert, delete가 느리다. (O(n))
  
  • 삽입 위치를 비워두고 그 뒤에 element들을 한 칸씩 밀어야 되기 때문에

 

 

Linked List(연결 리스트)의 특징

• read, write할 때에 head node부터 시작하여 원하는 노드를 찾아야 하기 때문에 느리다.
  • O(n)
• insert, delete가 빠르다.(노드를 찾는 과정 미포함)
  • O(1)

 

4. Pointer structures (포인터 구조)

>>> s = set()

우리는 일반적으로 s가 set type의 변수라고 말합니다. 즉, s는 set(집합)입니다. 그러나 이는 엄격히 따지면 맞지 않는 말입니다.

 

변수 s는 오히려 set에 대한 reference(a safe pointer)라고 말할 수 있습니다. 우리말로는 참조라고도 하죠.

set type의 contructor(생성자)는 메모리 안 어딘가에 set 하나를 만들고나서 그 set이 만들어진 메모리 위치를 반환합니다.

 

이 위치가 바로 변수 s에 저장되는 것입니다. python은 우리로부터 이러한 complexity(복잡한 내부사정)를 숨깁니다.

그렇기 때문에 ADT의 맨 앞 글자가 Abstract, 즉 '모호하다'라고 표현되는 것입니다.

 

우리는 이 사실 덕분에 s는 set이며 모든 것이 잘 수행될 것이라 안전하게 가정할 수 있는 것입니다.

 

pointer structure들에 대한 몇가지 이점들이 존재합니다.

• 우선적으로, 그 이점은 sequential storage space(연속적인 저장 공간)을 요구하지 않는다는 것에 있다.
• 두 번째로는 규모가 작게 시작할 수 있고 우리는 구조체에 더 많은 node를 추가하면서 임의로 계속 확장할 수 있다.
• 등등...

그러나 pointer가 가진 이러한 유연성은 곧 cost(비용)로 다가오는데요, 그 주소를 저장하기 위한 추가적인 공간을 필요로하기 때문입니다.

 

예를 들어, 만약 integer(정수) 타입의 요소를 가지는 리스트를 가지고 있다면, 각 노드는 정수를 저장하면서 공간을 채울 것입니다.

물론, next node에 대한 pointer를 저장하기 위한 추가적인 정수 또한 저장된다.

 

5. Node class (노드 클래스)

node의 단순한 형태는 next node와의 단 하나의 연결만을 가지는 node입니다.

 

우리가 pointer에 대해 앞서 보았듯, 노드에 저장되는 string들은 사실 노드에 "저장"되는 개념이 아니라, 실제 string에 대한 pointer가 있는 것입니다. (즉 string을 가리키는 포인터가 있는 것)

 

다음 diagram에 두 개의 node를 가진 예제를 생각해 보겠습니다.

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

위 코드는 Node라는 클래스를 정의한 것이며 생성자에서 멤버 변수를 초기화합니다. 해당 멤버 변수로는 그 안의 값의 위치를 가리키는 data 변수와 다음 노드 위치를 가리키는 next 변수가 있습니다.

 

두 노드에 각자 문자열이 있는 모습

class Node:
    def __init__(self, data=None): #data는 local variable
        self.data = data  # self.data는 instance variable
        self.next = None

a = Node('eggs')

노드 인스턴스를 하나 생성할 때는 생성자 형태에 따라서 인자로 data 값을 넣어줍니다.

 

6. Singly linked list class (단일 연결 리스트 클래스)

list는 node와는 구별되는 컨셉입니다. 먼저 list를 이해하기 위해 매우 단순한 class를 만드는 것으로부터 시작하겠습니다.

우리는 첫 번째 노드에서 첫 번째 노드에 대한 reference를 유지하는 constructor(생성자)부터 시작합니다.(즉, 아래 코드에서 head)

class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.size = 0


words = SinglyLinkedList() # words.head -> None

적어도 단일 연결 리스트에서는 어떤 linked list에 접근하기 위해서 그 리스트의 head node가 제일 중요한데요, 모든 접근은 head node로 부터 시작합니다.

 

Insert(prev_node, data)

Insert의 인자로 생성하고자 하는 위치 바로 전의 노드를 넣습니다.

def insert(self, prev_node, data):
        node = Node(data)
        self.size += 1

        # insert as a non-head node
        if prev_node:
            node.next = prev_node.next
            prev_node.next = node
        # insert as the head node (empty or not)
        else:
            node.next = self.head
            self.head = node


words = SinglyLinkedList() # words.head -> None
words.insert(None, "eggs")
words.insert(words.head, "ham")

• 노드 instance 생성
• 크기를 1 증가
• if 중간에 삽입하는 경우
  • prev_node의 next pointer가 가리키는 값(None)을 새로 생성한 node의 next pointer가 가리키게 한다.
  • prev_node의 next pointer가 생성한 node를 가리키게 한다.
• elif 리스트의 맨 앞에 삽입하는 경우(빈 리스트이거나 맨 앞에 삽입)
  • prev_node가 None인 경우
  • 새로 생성할 node의 next pointer가 head(None)가 가리키던 걸 가리키게 하고,
  • head는 이제 생성한 node를 가리키게 한다.

삽입 전 리스트 모습

 

삽입 후 리스트 모습

 

Traverse()

현재 가리키는 노드를 의미하는 current 변수를 컨트롤 하여 연결 리스트를 순회합니다.

 def traverse(self):
        current = self.head
        while current:
            yield current.data
            current = current.next


words = SinglyLinkedList() # words.head -> None
words.insert(None, "eggs")
words.insert(words.head, "ham")
for word in words.traverse():
    print(word)

current가 옮겨가다가 None 값을 가지는 순간이 있을 건데, 그 순간 순회를 중단합니다.

 

 

Function returns: yield

return 키워드는 반환하면 해당 함수가 종료하기 때문에 경우에 따라서 불편한 상황이 생깁니다.

 

yield 키워드는  종료되지 않게 하고 싶을 때 사용하는 키워드입니다.

위 traverse() 코드를 보면 알 수 있지만 보통 for문의 iterable 객체를 함수의 리턴 값으로 사용할 때 그 리턴을 yield로 시키게 되면 다시 함수로 들어가게 됩니다.

 

• yield는 요구에 의해 one by one으로(하나씩) 반환한다.
  • Generator functions
  • 시간과 메모리 측면에서 좋다.

>>> def simple_generator():
        for n in range(4):
            yield n + 1

>>>
>>> for i in simple_generator():
        print(i, end=' ')
1 2 3 4

 

 

Delete(prev_node)

 

def delete(self, prev_node):
        self.size -= 1

        #delete a non-head node
        if prev_node:
            prev_node.next = prev_node.next.next

        # delete the head node
        else:
            self.head = self.head.next


words.delete(words.head)

삭제하려는 노드 이전 노드가 head가 아닌 경우

삭제하려는 노드 이전 노드가 head가 아닌 경우, prev_node의 next point를 prev_node의 next pointer가 가리키던 노드를 가리키게 합니다.

 

def delete(self, prev_node):
        self.size -= 1

        #delete a non-head node
        if prev_node:
            prev_node.next = prev_node.next.next

        # delete the head node
        else:
            self.head = self.head.next


words.delete(None)

삭제하려는 노드가 head 노드인 경우 prev_node가 None입니다. 그 경우 head는 head가 가리키던 노드의 next 포인터가 가리키는 값을 가리키게 됩니다.

 

전체 코드

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None
        
class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.size = 0
        
    def insert(self, prev_node, data):
        node = Node(data)
        self.size += 1

        # insert as a non-head node
        if prev_node:
            node.next = prev_node.next
            prev_node.next = node
        # insert as the head node (empty or not)
        else:
            node.next = self.head
            self.head = node

    def traverse(self):
        current = self.head
        while current:
            yield current.data
            current = current.next

    def delete(self, prev_node):
        self.size -= 1

        #delete a non-head node
        if prev_node:
            prev_node.next = prev_node.next.next

        # delete the head node
        else:
            self.head = self.head.next

words = SinglyLinkedList() # words.head -> None
words.insert(None, "eggs")
words.insert(words.head, "ham")
for word in words.traverse():
    print(word)
words.delete(words.head)

 

7. Doubly linked lists (이중 연결 리스트)

Doubly linked list는 양방향으로순회 할 수 있습니다. Doubly linked list에서 한 노드는 그것의 이전 노드(prev_node)를 통해 그 노드의 track을 유지하는 변수를 별도로 가지지 않고도 필요에 의해 언제든지 참조할 수 있습니다.

 

앞선 단일 연결 리스트에서는 계속 prev_node를 통해 연산을 해야해서 헷갈렸는데 이전 노드를 가리키는 포인터를 도입하여 그 단점을 보완한 구조인 것입니다.

class Node(object):
    def __init__(self, data=None, next=None, prev=None):
        self.data = data
        self.next = next
        self.prev = prev

코드를 보시면 prev 포인터가 하나 추가된 것을 확인하실 수 있습니다.

 

 

8. Circular lists (원형 리스트)

맨 마지막 노드가 NULL을 가리키는 것이 아니라 맨 처음 노드를 가리키는 구조입니다.

 

• Circular singly linked list

• Circular doubly linked list

 

insert(prev_node, data)

class CircularList:     #Circular Singly Linked List
    def __init__(self):
        self.head = None
        self.size = 0

    def insert(self, prev_node, data):
        node = Node(data)
        self.size += 1

        #list is not empty
        if prev_node:
            node.next = prev_node.next
            prev_node.next = node
        #list is empty
        else:
            node.next = node # 자기 자신을 가리킴
            self.head = node

words = CircularList()
words.insert(None, "eggs")
words.insert(words.head, "ham")
words.insert(words.head, "spam")

 

SLL(Singly Linked List) vs. CSLL(Circular Singly Linked List)

• SLL: 새로운 노드를 head node 다음에 삽입하고 싶으면 prev_node로 None을 전달하면 된다.
• CSLL: 노드가 원형 순환구조로 이어져 있기 때문에 head 다음에 삽입하는 것이나 중간에 삽입하는 것이나 똑같지만 , CSLL에서 prev_node 인자로 None을 넘긴다는 것은 해당 list 가 비어있음을 의미한다.

 

Traverse()

def traverse(self):
    current = self.head
    while True:
        yield current.data
        if current.next == self.head:
            break
        else:
            current = current.next


words = CircularList()
words.insert(None, "eggs")
words.insert(words.head, "ham")
words.insert(words.head, "spam")
for word in words.traverse():
    print(word)

원형 리스트의 traverse()에서 stop 조건은 current 노드(현재 순회 중인 노드)의 다음 노드가 head일 때입니다.

 

Delete(prev_node)

def delete(self, prev_node):
    self.size -= 1

    # delete a non-head node
    if prev_node.next != self.head
        prev_node.next = prev_node.next.next

    # delete the head node
    else:
        # multiple nodes in list
        if prev_node != self.head:
            self.head = self.head.next
            prev_node.next = self.head
        # only one node in list
        else:
            self.head = None


words.delete(words.head)
for word in words.traverse():
    print(word)

head node를 delete하는 경우에도 리스트에 노드가 하나만 있는 경우와 여러개가 있는 경우로 나뉘게 됩니다.

 

리스트에 여러 개의 노드가 있는 경우

head 노드 삭제 전 모습

삭제 과정

삭제 후 모습

 

리스트에 head 노드 하나만 있는 경우

리스트에 head 노드 하나만 있는 경우

관련된 문제

• 백준 1158번 요세푸스 문제

1158번: 요세푸스 문제

 

풀이

n, k 인 경우에 노드를 하나씩 삭제해 가기 때문에 k-1만큼씩 prev_node를 지정합니다.

n, k = map(int, input().split())

jo = []
for i in range(1, n+1):
    jo.append(i)

print('<', end='')

index = 0

while len(jo) > 0:
    index += k - 1
    if len(jo) <= index:
        index %= len(jo)

    if len(jo) > 1:
        print(jo.pop(index), end=', ')
    else:
        print(jo.pop(index), end='')

print('>', end='')

 

9. Circular List using Python List (파이썬 리스트를 사용한 원형 리스트 구현)

Python List Methods

fruits = ['orange', 'apple', 'banana']
print(len(fruits))
# 3

fruits.append('kiwi')
print(fruits)
# ['orange', 'apple', 'banana', 'kiwi']

fruits.insert(2, 'pear')
print(fruits)
# ['orange', 'apple', 'pear', 'banana', 'kiwi']

print(fruits.pop(1))
# 'apple'
print(fruits.pop())
# 'kiwi'
fruits.remove('banana')
print(fruits)
# ['orange', 'pear']

 

Circular list: Increasing the index trick

fruits = ['orange', 'apple', 'pear', 'banana', 'kiwi']

index = 3
print(fruits[index])
# 'banana'

index += 2
print(fruits[index])
# IndexError: list index out of range

위 코드처럼 아무생각없이 index값을 늘리다 보면은 파이썬에서는 out of range 에러가 발생하기 마련입니다.

하지만 아래 코드 처럼 modulo 연산을 적용하면 이 문제를 피할 수 있고 이는 리스트를 계속해서 순회하는 경우 굉장히 유용한 트릭입니다.

index = 3
index += 2
if index >= len(fruits):
    index = index % len(fruits)

print(fruits[index])
# 'orange'

 

 

Circular list: pop

fruits = ['orange', 'apple', 'pear', 'banana', 'kiwi']

index = 3
fruits.pop(index)
# 'banana'

print(fruit[index])
# 'kiwi'

print(fruits.pop(index))
# 'kiwi'

print(fruits[index])
# IndexError: list index out of range

fruits = ['orange', 'apple', 'pear', 'kiwi']
print(fruits.pop(index))
# 'kiwi'

if index == len(fruits):
    index = 0

print(fruits[index])
# 'orange'

 

Example

words = []
words.append('eggs')
words.append('spam')
words.append('ham')

index = 0
while len(words) > 0:
    index += 2
    if index >= len(words):
        index %= len(words)

    print(words.pop(index))
    if index == len(words): #can be skipped
        index = 0

ham
eggs
spam