파이썬으로 연결리스트 만들기 1탄(자료구조 / 단순 연결리스트 / 이중 연결리스트 / 추가 / 삽입 / 삭제 / 접근)

파이썬의 클래스에 대해서 익숙해지는 시간을 가지기 위해서 간단한 자료구조인 Linked List, 연결리스트에 대해서 알아보도록 하겠습니다.

 

연결리스트는 각 노드를 선으로 연결한 것이라 할 수 있습니다.

그림으로 표현하면 다음과 같습니다.

저 그림을 조금 더 자세히 표현하면

이렇게 표현할 수 있고 이 그림은 단방향으로 연결되어 있어서 단순 연결리스트 또는 Singly Linked List 라고도 합니다.

 

저기 사각형 하나는 노드(Node)라고 합니다. 연결리스트는 노드들이 연결된 것이고 노드에는 값과 다음 노드를 가리키는 정보가 들어있습니다. 노드가 많이 필요할 수 있으니까 이를 class로 만들면 편합니다.

 

클래스를 만들 때는 속성과 행동을 봐야합니다. Node 클래스의 속성은 값과 다음 노드를 가리키는 정보 두 개가 있으며 행동은 딱히 하는 일이 없습니다. 단순이 정보를 가지고 있을 뿐입니다. 속성은 인스턴스 변수로 표현할 수 있으니까 다음과 같이 Node 클래스는 다음과 같이 작성할 수 있습니다.

class Node:
    def __init__(self, data):
        self.data = data  # 노드의 값
        self.next = None  # 다음 노드를 가리키는 정보

이 Node 클래스만을 가지고 연결리스트를 구현할 수 있습니다!(?)

class Node:
    def __init__(self, data):
        self.data = data  # 노드의 값
        self.next = None  # 다음 노드를 가리키는 정보


# 우선 노드 생성
n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n4 = Node(4)

# 연결하자!
n1.next = n2
n2.next = n3
n3.next = n4

# 확인하기
print(n1.next.next.data)  # 연결이 되어있는 것을 볼 수 있음

할 수 있는데 모든 과정이 수동으로 이루어져야 하기 때문에 상당히 귀찮습니다. 때문에 연결리스트도 class로 구현합니다.

 

연결리스트는 머리와 꼬리를 가지고 있습니다. 이를 head 노드, tail 노드라고 합니다. 따라서 위의 그림을 조금 더 자세하게 표현하면 다음과 같습니다.

이게 단순 연결리스트의 모습입니다.

 

책 마다, 만드는 사람 마다 거의 구현하는 코드가 다르며 똑같이 만드는 사람을 보질 못했습니다. 이 점을 미루어보았을 때 자료구조는 그 자료의 틀을 깨지 않는 선에서 코드를 구현하면 될 것 같습니다. 

 

연결리스트의 핵심은 노드를 연결하는 것입니다. 대표적인 4가지 기능으로 추가/삽입/삭제/접근의 기능이 있으며 그 외 나머지 기능은 필요하다 싶으면 구현하면 됩니다. (어떤 책은 추가를 할 때 기준노드의 앞에 뒤에 추가 연산으로 추가, 삽입을 퉁치며 어떤 책은 tail이 없는 경우도 있습니다. 즉 노드를 연결하는 과정이 연결리스트이므로 해당 부분을 깨지 않는 이상 모두 괜찮다고 봅니다.)

 

연결리스트의 속성과 행동을 다시 정리하겠습니다.

속성

-> head 노드

-> tail 노드

-> 노드의 갯수

행동

-> 노드 추가

-> 노드 삽입

-> 노드 삭제

-> 노드 접근

-> 연결리스트 길이

-> 연결리스트가 비었나?

-> 연결리스트 출력

 

속성은 인스턴스 변수, 행동은 메소드로 구현이 가능하므로 우선 속성부터 구현해보겠습니다.

class Node:
    def __init__(self, data):
        self.data = data  # 노드의 값
        self.next = None  # 다음 노드를 가리키는 정보


class LinkedList:
    def __init__(self):
        # 연결리스트를 처음 생성 시 아무것도 없으므로 다음과 같이 초기화 할 수 있다.
        self.head = None
        self.tail = None
        self.count = 0

Node 클래스는 당연히 가지고 있어야 합니다. 그 이유는 노드를 생성하기 위함입니다.

 

차후 추가 연산부터 차근차근 구현해보도록 하겠습니다.