[자료구조] 단방향 연결리스트(Singly Linked List)란? 파이썬으로 구현하기

목표

단방향 연결리스트의 개념에 대해서 이해해보고 파이썬으로 구현해보도록 하겠습니다.

 

목차                                                                                               클릭하면 해당 목차로 이동합니다.

단방향 연결 리스트란?(Singly Linked List)

 

파이썬으로 구현하기

 

정리

 

개요

앞서 순차적 자료구조인 리스트와 배열에 대해서 이해하고 스택과 큐에 대해서 공부하고 예제를 풀어보았습니다.

이번 포스팅에서는 단방향 연결리스트에 대해서 알아보도록 하겠습니다.

연결리스트는 배열과 유사하지만, 연속된 공간에 메모리를 차지하고 인덱스를 통해 상수시간 내에 값을 처리한다는 특징이 있습니다. 반면, 연결리스트는 메모리 상에 흩어져 있지만 연결되어 있다는 특징이 있습니다. 이에 대한 부분을 자세히 알아보도록 하겠습니다.

 

단방향 연결 리스트란?(Singly Linked List)

연결리스트는 단방향 연결리스트와 양방향 연결리스트로 구분됩니다. 말 그대로 한 방향으로만 이동할 수 있는지, 앞 뒤로 이동할 수 있는지에 대해 구분해놓은 것입니다. 이번 포스팅에서는 한 방향으로만 움직일 수 있는 연결리스트인 단방향 연결리스트에 대해서 알아보도록 하겠습니다.

 

앞서 말씀드렸다싶이, 메모리에 순차적으로 저장되는 배열과는 달리 연결리스트는 메모리 상에 흩어져있습니다. 대신 서로 연결되어 있는데요. 메모리 상에 흩어져 있는 각각의 덩어리(데이터)를 "노드"라고 합니다. 이 노드들은 다음 노드의 주소를 알고 있습니다. 이렇게 처음 노드부터 다음 노드, 그 다음 노드를 타고 이동하면서 탐색할 수 있는 것입니다. 결국 노드는 각 노드의 데이터값(Key)와 다음 노드의 주소(Link)를 갖고 있는 것입니다. 다음 노드로만 이동할 수 있는 것이 단방향 연결리스트(Singly Linked List)입니다. 다음 노드로만 이동하기 때문에 순서가 있겠죠? 그림으로 확인하면 더욱 이해하기 쉽습니다.

▲ 단방향 연결리스트, Singly Linked List

그림에서 보시는 것처럼 다음 노드를 가리키고 탐색하는 구조입니다.

맨 처음 노드, 즉 1번 인덱스는 Head Node라고 합니다. 첫 번째 노드의 주소와 노드가 몇 개 있는지(사이즈)의 값을 가지고 있습니다. 

+ 0번 인덱스는 실제 노드가 아니라 이 노드들을 관리하는 객체라고 보시는게 좋을 것 같습니다. 실제 첫번째 노드는 1번 노드입니다.

 

맨 마지막 노드인 3번 인덱스는 마지막 노드로 Tail Node라고 합니다. 마지막 노드는 다음 노드가 없기 때문에 다음 노드의 주소(링크)의 값이

None이 됩니다. 그림에서는 공집합으로 표현했습니다.

 

그럼 굳이 배열을 안쓰고 연결 리스트를 만드는 이유는 뭘까요?

만약, 제가 배열의 2번 자리에 무언가 새로운 값을 넣고 싶다면 2번부터 그 뒤의 값들을 모두 한 칸씩 뒤로 밀고 새로운 값을 삽입해야합니다. 그냥 2번 자리에 Push를 한다면, 원래 2번 자리의 값을 없어지기 때문입니다.

반면, 연결리스트는 2번자리에 새로운 값을 넣고자 한다면 새로운 노드를 생성하여 1번 노드의 링크를 새로운 노드와 연결하고 새로운 노드는 2번 노드의 주소를 갖고 있으면 됩니다. 훨씬 간결하고 빨라진 것을 알 수 있습니다.

대신, 중간의 값을 탐색하기 위해서 인덱스로 접근할 수 없고 처음(head)부터 탐색해나가야한다는 단점이 있습니다.

추가로, 각 노드들은 값을 1개씩 갖는 것이 아닌 추가적인(여러개의) 값을 가질 수 있습니다.

예를 들면 이름, 학번, 학과 등의 값을 한 노드에 담을 수 있다는 뜻입니다. 각각의 노드가 객체의 역할을 하는 것입니다.

 

단방향 연결리스트에도 삽입·삭제·탐색 연산을 지원합니다. 스택과 마찬가지로 Push, Pop이 존재합니다.연결리스트의 경우 방향이 존재하기 때문에 앞에 추가할수도, 뒤에 추가할수도 있습니다. 삭제도 마찬가지구요.그래서 상황에 따라 4가지 메소드가 존재합니다.

pushFront 

새로운 노드를 앞에 추가하는 메소드입니다. 그렇다면, Head Node가 새로운 노드를 가리키게 하고 새로운 노드는 기존의 첫번째 노드를 가리키게 하면 됩니다. 그리고 총 노드의 개수에 1을 더하면 됩니다.

pushBack

새로운 노드를 뒤에 추가하는 메소드입니다. 처음 연결 리스트를 클래스로 구현할 때 마지막 노드(Tail Node)의 값을 알고 관리해주면 조금 편리하겠지만, 이번 경우에는 그렇지 않습니다. 따라서, Tail Node를 찾아야합니다. Tail Node는 다음 노드의 주소(Link)를 갖고 있지 않기 때문에 None을 가리키고 있습니다. 이 특징을 이용해서 Tail Node를 찾을 수 있습니다. Tail Node를 찾으면, 새로운 노드를 가리키게 하고 새로운 노드는 None을 가리키면 됩니다. 그리고 총 노드의 개수에 1을 더하면 됩니다.

popFront

첫번째 노드를 삭제하는 메소드입니다. Head node가 두 번째 노드를 가리키게 하고 첫번째 노드는 삭제하면 됩니다. 그리고 총 노드의 개수에 1을 빼면 됩니다.

popBack 

마지막 노드를 삭제하는 메소드입니다. 마찬가지로, 맨 뒤의 노드를 알 수 없기 때문에, 위와 같은 방법으로 Tail Node를 찾아서 삭제하고, 그 전의 노드가 None을 가리키게하면 됩니다. 그리고 총 노드의 개수에 1을 빼면 됩니다.

search

특정 노드를 위해서 탐색하는 메소드입니다. 단방향 연결리스트이기 때문에 Head Node에서 뒤 노드로 순서대로 이동할 수 밖에 없습니다. 이후 글에서 나오겠지만 제너레이터(Generator)를 이용해서 for문을 사용해 특정 노드를 편하게 탐색할 수 있습니다.

 

 

파이썬으로 구현하기

단방향 연결 리스트를 파이썬으로 구현해보도록 하겠습니다.

스택, 큐같은 경우에는 1개의 클래스로 구현할 수 있었지만, 이번에는 2개의 클래스가 필요합니다.

각각의 노드를 생성하는 클래스, 노드들을 연결하고 관리하는 클래스가 필요합니다.

이래서 각각의 노드들이 객체의 역할을 하는 것과 비슷한 것 같습니다.

 

▲ 노드를 생성하는 Node 클래스

노드를 생성하는 Node 클래스입니다.

노드를 생성하기 위해 Key값과 Value값을 받습니다. Key도 값이지만, 그 노드를 대표하는 값입니다. 이를테면, 성적표에는 이름, 학번, 국어성적, 수학성적 등이 있겠죠? 이 중에서도 학번을 통해서 각 노드의 성적을 확인할 수 있을 것입니다. 이런 경우에는 학번이 Key값이 되는 것입니다. 그래서 노드를 생성할 때 생성자에서 key, value값을 생성하는 것입니다. 처음 노드가 생성되면 지금 생성된 노드밖에 없기 때문에, 링크(다음 노드의 주소)는 None입니다. 2번째 노드부터는 노드를 관리하는 클래스에서 생성할 때, 이전 노드의 링크를 새로 생성하는 노드의 주소로 변경해주게됩니다.

 

생성자는 클래스를 생성할 때마다 봐서 익숙하겠지만, __str__는 조금 낯설 수 있습니다. 뭔가 눈치껏 봐도 메소드 이름 앞뒤에 "__"가 붙게 되면 뭔가 특별하다는 것을 눈치챌 수 있습니다. 이런 메소드를 스페셜 메소드라고 합니다. 눈에 보이지 않는 특별한 역할을 할 수 있는 메소드란 뜻입니다. 생성자만 봐도, 따로 호출하지 않아도 객체가 생성되면 자동으로 생성자 메소드를 실행하면서 초기값을 설정할 수 있는 것과 같습니다.마찬가지로, __str__ 메소드는 다음과 같은 역할을 합니다.노드를 생성해서 사용하다보면 노드의 key값을 알아야할 때가 있습니다. 이 경우에 우리는 print(node.key)로 적어서 확인할 것입니다. 하지만 __str__메소드를 생성하게 되면 그냥 print(node)라고만 적어도 노드의 key값을 확인할 수 있습니다. 사실상 print(node.__str__())와 같은 역할을 하게 됩니다. 따라서, __str__ 메소드는 클래스 자체의 내용을 확인하고 싶을 때 사용하는 메소드입니다.

 

 

▲ 노드를 관리하는 클래스, SinglyLinkedList

노드를 관리하는 클래스인 SinglyLinkedList의 일부입니다. 노드를 관리하기 때문에, 첫 번째 노드의 주소와 사이즈를 갖고 있습니다. 아직 생성된 노드가 없기 때문에 head가 None을 가리키고 있습니다.

__iter__

메소드도 익숙하지 않은 메소드입니다. 저 같은 경우에는 yield라는 키워드를 이번에 처음 사용했습니다.

생성자와 마찬가지로 "__"이 붙어 있기 때문에 스페셜 메소드라는 것을 알 수 있습니다. 사실, 이 메소드는 제너레이터(Generator)입니다. 탐색을 위해for 문을 사용하기 위해서 제너레이터를 사용해서 노드들을 iterable하게 만들어줍니다. 

무슨 뜻일까요? 우리는 보통 for i in List: 와 같이 사용합니다. 이건, List라는 리스트안에 있는 값을 한개씩 i에 넣어서 이용하는 것입니다. List에 문자열이 들어와도 한 글자씩 확인할 수 있습니다. 이렇게 나누어서 셈을 할 수 있는 것을 iterable하다고 말합니다. 이상한 값을 넣으면 에러메세지에도 iterable하지 않다고 나오는 것을 본 적이 있을것입니다. 여기서도 각 노드들을 iterable하게 만들어주기 위해서 반복문을 통해 head부터 tail까지 쭉 탐색하는 것입니다. 반복문 안에 있는 yield 키워드는 return과 비슷한 역할을 한다고 생각하면 됩니다. for i in Node와 같이 사용했다면, yield v 를 할 때마다, 그 노드의 값이 i에 대입되는 것입니다.

__str__

메소드는 여기서도 보이는데요. 모양이 조금 특이해졋습니다. .join 메소드가 사용되었기 때문인데요.

.join 메소드는 연결해주는 역할을 한다고 생각하면 됩니다. join메소드의 매개변수에 리스트 내포가 되어있기 때문에 조금 복잡해보이는데요. 각 노드들을 출력할 때, 각 노드들 사이에 "->"와 같이 화살표를 넣어 가독성을 높이기 위함입니다.

__len__

메소드는 말 그대로 멤버변수인 size의 값을 리턴하는 역할을 합니다. A라는 SinglyLinkedList를 생성하고 len(A)를 한다면 노드의 개수(A.size)가 리턴됩니다.

 

다음은 Push 메소드를 확인해보도록 하겠습니다.

▲ SinglyLinkedList의 Push 메소드

새로운 노드를 추가하는 Push 메소드입니다. 앞에 넣을지, 뒤에 넣을지에 따라 2개의 메소드로 구분할 수 있습니다.

 

먼저, 앞에 새로운 노드를 추가하는 pushFront 메소드입니다.새로운 노드를 추가하고, 새로운 노드는 기존의 첫번째 노드를 가리키게됩니다. 그리고 전체 노드의 head를 새로운 노드로 변경하고 사이즈를 추가하는 것을 확인할 수 있습니다.

 

다음은 뒤에 새로운 노드를 추가하는 pushBack 메소드입니다.먼저 새로운 노드를 추가합니다. 이 때, 생성된 노드가 하나도 없다면, 새로운 노드가 Tail Node이자 Head Node입니다. 그렇기 때문에, 그냥 전체 노드의 head를 새로운 노드로 변경하고 사이즈를 늘리고 메소드를 마무리하면 됩니다. 그렇지 않다면, 제일 마지막 노드인 Tail Node를 찾아야합니다. 그래서 링크가 None인 노드를 찾아서, Tail Node가 새로운 노드를 가리키게 한 뒤, 새로운 노드는 None을 가리키게하면 됩니다. (Node 클래스를 생성할 때, 초기값이 None이었기 때문에 따로 작업하지 않습니다.)

 

▲ SinglyLinkedLis의 Pop 메소드

다음은 기존 노드를 제거하는 Pop메소드입니다. 마찬가지로 앞, 뒤의 노드를 제거하는지에 따라 2개의 메소드로 구분됩니다.

 

먼저, 앞의 노드를 제거하는 popFront 메소드입니다. 항상 무언가를 제거할때는 신중해야합니다. 노드를 제거하려고 하는데 기존에 노드가 없으면 제거할 것도 없습니다. 그래서 None을 리턴하고 마무리합니다.그렇지 않다면 Head Node를 제거해야합니다. 어떤 값이 없어졌는지 알아야하기 때문에, x와 key라는 지역변수를 생성해서 head의 key값을 저장한 뒤리턴합니다. 전체 노드의 Head를 다음 노드에 가리키게 한 뒤, 기존 Head Node를 삭제합니다. del x를 통해서 메모리에서 아예 삭제한 뒤 마무리합니다.

 

다음은 뒤의 노드를 제거하는 popBack 메소드입니다. 맨 뒤 노드(Tail Node)를 제거하면, 그 이전의 노드가 Tail Node가 되고 None을 가리키게 됩니다. 이 노드를 prev라고 하겠습니다.  길이를 확인할 때 popFront처럼 해도 되지만, __len__메소드를 정의했기 때문에 위처럼 len(self)처럼 사용해도 길이를 리턴받습니다. 마찬가지로 길이가 0이면 None을 리턴하고 종료합니다. 그렇지 않다면 반복문을 통해서 Tail Node를 찾아야합니다. 우리는 마지막 노드를 찾으면 제거하고 그 이전의 노드를 Tail Node로 만들기로 했습니다. 하지만 노드가 1개라면? 이전의 노드는 없고 Tail Node는 Tail Node이자 Head Node입니다. 그래서 그냥 Head Node를 삭제하면됩니다. 그렇지 않다면 정상적으로 반복문을 이용해서 Tail Node를 찾습니다. 이 과정에서 Tail Node 이전의 노드(Prev)도 계속 따라갑니다. 머릿속에 그려지시나요? Tail Node를 찾기 위해 다음 노드로 이동할 때, 그 뒤에서 계속 따라오는 모양입니다. 이런 구조를 "Running Technique"이라고 합니다. 이렇게 Tail Node를 찾게되면 기존의 Tail Node를 삭제하고 Prev Node를 Tail Node로 만든 뒤, 삭제된 Tail Node의 Key값을 반환한 뒤 종료합니다.

 

▲ SinglyLinkedList의 탐색연산

마지막으로 탐색연산입니다. 단방향 연결리스트이기 때문에 Head Node부터 Tail Node까지 이동하면서 순차적으로 탐색할 수밖에 없습니다. 해당 key값과 일치하면 리턴하고 마무리합니다.

처음 클래스를 생성할때 __iter__라는 제너레이터(Generator)를 선언했기 때문에 이 객체를 생성하면 반복문을 통해서 탐색할 수 있습니다.

 

정리

이렇게 단방향 연결 리스트에 대해서 알아보았습니다. 앞으로 배울 자료구조들이 많이 남아 있는데, 다양한 자료구조들을 어떻게 사용하는지에 따라 천차만별인 것 같습니다. 다음 포스팅에서는 양방향 연결리스트에 대해서 알아보고 관련된 예제를 해결해보는 시간을 갖도록 하겠습니다.

 

*한국외대 신찬수 교수님의 Data Structures with Python 강의를 참고하여 포스팅하였습니다.