[SW 정글 28일차] 연결리스트 만들어보기

연결리스트, 나는 파이썬에서 리스트 자료형을 쓰면서 인덱스로 원소에 접근할 수 있고 순서도 있으니 굳이 연결리스트가 따로 있어야 했나라는 의문을 가지고 있었다.

하지만, 오늘 연결리스트에 대해 공부하고 난 후, 기존에 있던 배열과 연결리스트의 차이점을 알게 되었고 연결리스트의 확장으로 이중연결리스트, 환형 연결리스트, 환형 연결리스트까지 살펴볼 수 있는 시간을 가졌다.

 

 

 

 

1. 연결 리스트란?

연결 리스트를 정의하기 전에 리스트라는 것은 순서가 있는 데이터를 늘어놓은 자료구조이다.

연결 리스트는 구조가 단순한 리스트 중 하나로 데이터가 순서대로 나열되고 각 데이터가 화살표로 연결되어 자신의 뒤에 어떠한 데이터가 오는지 알 수 있는 리스트이다.

연결 리스트의 기본 구조는 위의 그림과 같다.

연결 리스트에서 각각의 원소를 노드(node)라고 하고 각각의 노드가 가지고 있는 것은 데이터와 자신의 뒤에 오는 노드를 가리키는 포인터이다.

 

연결리스트는 배열을 이용하여 만들 수 있다.

이렇게 하면 자신의 인덱스에서 +1한 원소가 바로 뒤 노드라고 정의할 수 있다.

그러면 삽입과 삭제 시에는 어떻게 해야할까?

위 그림처럼 삽입 시에 데이터를 옮겨야하는 작업이 필요하므로 효율적이지 않다.

그러면 지금부터 포인터를 이용한 연결 리스트와 커서를 이용한 연결 리스트를 알아보자.

 

 

 

 

2. 포인터를 이용한 연결 리스트

포인터를 이용한 연결 리스트는 노드마다 뒤쪽 노드를 가리키는 포인터가 포함되도록 구현하는 것이다.

포인터를 이용하게 되면 연결 리스트에 삽입할 때 노드용 인스턴스를 생성하고 데이터를 삭제할 대 노드용 인스턴스를 없애면 되므로 앞에서 배열을 이용한 연결 리스트의 단점을 해결할 수 있다.

위의 사진은 노드를 나타낸 것인데 각 노드에는 data와 다음에 오는 노드를 가리키는 next가 있다.

data는 데이터 자체가 담기는 것이 아닌 데이터에 대한 참조이고 next는 다음 노드에 대한 참조이다.

 

노드를 생성하는 Node 클래스와 연결 리스트를 만들고 기능을 구현하는 LinkedList 클래스를 코드로 구현하면 아래와 같다.

class Node:

    def __init__(slef, data, next):
        # 데이터 자체를 포함하는 것이 아닌 데이터에 대한 참조
        self.data = data
        # 뒤쪽 노드에 대한 참조
        self.next = next

class LinkedList:
    def __init__(self):
        # 노드의 개수
        self.no = 0
        # 머리 노드
        self.head = None
        # 주목 노드
        self.current = None

    def __len__(self):
        return self.no

    def search(self, data):
        cnt = 0
        ptr = self.head
        // 선형검색진행
        while ptr is not None:
            if ptr.data == data:
                self.current = ptr
                return ctr
            cnt += 1
            ptr = ptr.next
        return -1

    def __contain__(self, data):
        # 연결리스트에 data가 포함되어 있는지 확인
        return self.serach(data) >= 0

    def add_first(self, data):
        ptr = self.head
        self.head = self.current = Node(data, ptr)
        self.no += 1

    def add_last(self, data):
        ptr = self.head
        if ptr is None:
            self.add_first(data)

        else:
            while ptr is not None:
                ptr = ptr.next

            ptr.next = self.current = Node(data, None)
            self.no += 1

    def remove_frist(self):
        if self.head is not None:
            self.head = self.current = self.head.next
            self.no -= 1

        else:
            print("현재 빈 연결리스트이므로 삭제할 노드가 없습니다.")

    def remove_last(self):
        if self.head is not None:
            if self.head.next is None:
                self.head = None
            else:
                ptr = self.head
                pre = self.head

                while ptr is not None:
                    pre = ptr
                    ptr = ptr.next

                pre,next = None
                self.current = pre
                self.no -= 1

    def remove(self, p):
        if self.head is not None:
            if p is self.head:
                self.head = None
            else:
                ptr = self.head
                
                while ptr.next is not p:
                    ptr = ptr.next
                    if ptr is None:
                        return
                    ptr.next = p.next
                    self.current = ptr
                    self.no -= 1

    def remove_current_node(self):
        self.remove(self.current)

    def clear(self):
        while self.head is not None:
            self.remove_first()
        self.current = None
        self.no = 0

    def next(self):
        if self.current is None or self.current.next is None:
            return False
        self.current = self.current.next
        return True

    def print(self):
        ptr = self.head

        for ptr.next is not None:
            print(ptr.data)
            ptr = ptr.next

 

 

 

 

3. 커서를 이용한 연결 리스트

위에서 알아본 포인터를 이용한 연결 리스트는 노드를 삽입하고 삭제할 때마다 내부에서 노드용 인스턴스를 생성하고 없애는 작업이 이루어진다.

이러한 작업을 위해 메모리를 확보하고 제거하는데 쓰이는 비용을 신경을 안쓸 수가 없다.

커서를 이용한 연결 리스트는 각 노드를 배열 안의 원소에 저장하는 방식이다.

분명 처음에 배열을 이용하여 연결 리스트를 구현했을 때 삽입, 삭제 시에 일부분의 데이터를 옮기는 작업이 필요하여 비효율적이였다.

지금 볼 커서를 이용한 연결 리스트는 어떻게 구현될까?

위 그림을 보면 배열에 각각의 원소에는 노드가 저장되고 노드를 보면 데이터와 다음 노드의 인덱스를 저장하는 커서가 있다.

커서는 int형 정수값인 인덱스로 나타낸 포인터를 의미한다.

꼬리 노드의 커서는 -1이고 위 그림에서는 인덱스 3번에 있는 노드가 꼬리 노드가 되는 것이다.

머리 노드를 나타내는 head에 저장된 값도 커서이다. 즉, 인덱스 1번에 있는 것이 머리 노드가 되는 것이다.

 

커서를 이용한 연결 리스트의 단점으로는 노드를 삭제하고 추가 시에 빈 공간들을 활용을 못하는 것이다.

이 단점을 해결하기위해 프리 리스트(free list)이다.

프리 리스트(free list)는 삭제된 레코드 그룹을 관리할 때 사용하는 자료구조로 삭제 후 비어 있는 배열의 문제를 해결할 수 있다.

기존에는 삭제되어 비어 있는 부분을 알 수 없어 단순히 마지막으로 채워진 노드 다음 인덱스에 새로운 노드를 삽입했다.

프리 리스트를 사용하면 노드를 삭제 시에 해당 노드가 존재했었던 배열의 인덱스를 저장한다.

이 후에, 새로운 노드를 삽입 시에 프리 리스트에 저장된 값이 있다면 해당 값에 해당하는 인덱스에 노드를 삽입하여 삭제 후에 비어 있는 배열 공간을 없앨 수 있다.

 

 

저번 기수 협력사 설명회 정리글을를 보니 '연결리스트는 왜 이진탐색이 안될까요?'라는 질문이 자료구조에서 가장 기초 적인 질문이라고 나와있었다.
오늘에서야 그 질문을 나도 대답할 수준으로 성장했다고 느꼈고 깊이 있게 파고들도록 노력했다.

---

[오늘의 나는 어땠을까?]

오늘은 이전부터 계획했던 연결리스트에 대해 공부하고 직접 만들어 보는 시간을 가졌다.

연결리스트를 공부해 본적은 있지만 오늘처럼 심도있게 공부를 하고 구현을 해 본적은 없는 것같다.

새로운 지식을 쌓았다는 것에 오늘도 성장했다고 느낄 수 있고 내일도 성장하기를 기대한다.

 

그리고 오늘 점심은 부모님이 오셔서 함께 식사를 했다.

2주에 한번씩 오신다고 하셨고 벌써 2주가 지났구나라는 생각이 들었다.

저번처럼 슬픈 감정이 밀려오지는 않았지만 내가 피곤해보이고 힘이 없는 모습을 보셔서인지 걱정의 눈초리를 느꼈다.

5개월 후, 내가 얻고자하는 것들을 모두 얻어 걱정의 눈초리가 대견함의 눈초리로 바뀌었으면 좋겠다.

단편적으로 취업에 성공했다라는 것이 아닌 내가 얼마나 성장했고 무엇을 느꼈는지를 알려주면 당연히 바뀔 것이다.

목표 성취를 위해 계속해서 성장하고 어제의 나보다 열심히 살자.

---

<참고 자료>

자료구조와 함께 배우는 알고리즘 입문 파이썬 편 (저자 Bohyoh Shibata, 옮김 강민)