[자료구조] Singly LinkedList(단순 연결 리스트)(Python)

* 개요

오늘부터 자료구조를 공부하기로 했다. 백준이나 프로그래머스 문제를 풀면서 자료구조와 알고리즘의 필요성에 대해 알게 되었기 때문이다. 백준 같은 경우 테스트 케이스가 워낙 방대하고 많기에, 자료구조와 알고리즘을 제대로 쓰지 않을 경우 시간 초과가 나는 경우가 종종 발생한다.(보통 테스트 케이스가 10만을 넘어간다면, 시간 복잡도 O(N^2)의 코드를 짰을 때 99퍼센트 확률로 시간 초과가 발생한다.) 자료구조는 컴공과 커리큘럼 기준으로 2학년 과정이지만, 필자는 학부 2학년 시절 코포자(코딩포기자)였기 때문에... 프로그래밍 관련 수업은 제대로 듣질 않았다.(그래서 학점이 개판이다...) 먼저 스터디 멤버들과 자료구조 스터디 커리큘럼에 대해 고민을 해보았는데,  먼저 LinkedList(연결 리스트)부터 공부하기로 하였다. 그 중 해당 포스트는 Singly LinkedList에 대해 다루고 있다. 우선 LinkedList의 개념부터 알아보도록 하자.

 

* LinkedList(연결 리스트)란 ?

LinkedList는 추상 자료형(Abstract Data Type)을 구현할 때의 기반이 되는 기초 선형 자료구조이다. LinkedList 말 그대로 어떠한 데이터 덩어리(노드)를 저장할 때 그 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식으로 자료를 저장한다.(노드의 포인터가 다음이나 이전의 노드와의 연결을 담당.) 예를 들어 한 반에 있는 학생들의 자료를 저장한다면, 학생 하나하나의 신상 명세 자료를 노드로 만들고, 1번 학생의 신상 명세 자료에 2번 학생 신상 명세가 어디 있는지 표시를 해놓는 방식이다. 더 쉽게 생각하면, 자료를 비엔나 소시지처럼 줄줄이 엮어놓은 것이다.

 

* Array(배열) vs LinkedList(연결 리스트)

자료구조 상에서 연결 리스트는 배열과 항상 비교된다.  눈에 보기 쉽게 배열과 연결 리스트의 특징을 표로 정리해보았다.

배열	연결 리스트
물리적 메모리 주소가 연속적이다.	물리적 메모리 주소가 연속적이지 않고 랜덤이다.
삽입/삭제의 시간복잡도는 O(N)이다.	삽입/삭제의 시간복잡도는 O(1)이다.
각 원소에 접근하는 것의 시간복잡도는 O(1)이다.  그 이유는 배열은 연속적인 메모리이고, 인덱스를 통해 데이터를 찾기 때문이다.	각 원소에 접근하는 것의 시간복잡도는 O(N)이다. 그 이유는 배열과 다르게 연속적인 메모리가 아니기 때문에, 데이터를 찾기 위해서는 모든 노드를 거쳐서 탐색해야 한다.
연결리스트에 비해 데이터의 탐색이 빠르다.	배열에 비해 데이터의 탐색이 느리다.
배열은 크기를 크게 키우는 것이 어렵다는 단점이 있다. 연속된 메모리 공간을 할당받아야 하는데 크기가 커지면 그만한 연속된 공간을 할당하기가 어려워지기 때문이다. 따라서 사용하지 않는 공간까지 예약해두고 있어야 하기 때문에 메모리의 낭비가 심하다.	배열에 비해 메모리의 낭비가 심하지 않다. 연속적인 메모리가 아니기 때문이다. 따라서 메모리의 낭비도 배열에 비해 심하지 않고, 연결 리스트의 길이를 동적으로 조절할 수 있다.

 

* Singly LinkedList(단순 연결 리스트)

Singly LinkedList(단순 연결 리스트)는 다음 노드에 대한 참조만을 가진 가장 단순한 형태의 연결 리스트이다. 가장 마지막 원소를 찾으려면 리스트의 마지막 노드까지 찾아가야 하기 때문에, 시간 복잡도는 O(N)이다. 보통 Queue(큐)를 구현할 때 해당 방법을 사용한다. 단순 연결 리스트는 Head 노드를 참조하는 주소를 잃어버릴 경우 데이터 전체를 못 쓰게 되는 단점이 있다. 다음 노드를 참조하는 주소 중 하나가 잘못되는 경우에도 체인이 끊어진 것처럼 뒷 부분의 자료들이 유실된다. 따라서 안정적인 자료구조는 아니라는 특징이 있다. 단순 연결 리스트를 사용한 파일 시스템이 존재하는데, 그것은 바로 FAT 파일 시스템이다. FAT 파일 시스템은 파일 내용 일부가 손상될 경우 파일의 상당 부분을 유실할 수 있고, 랜덤 액세스 성능도 낮다.

 

* 파이썬으로 구현한 Singly LinkedList(단순 연결 리스트)

단순 연결 리스트를 객체지향의 형태로 구현을 해보았다. 먼저 노드 부분부터 구현한다.

# 노드 구현
class Node :
    def __init__(self, data) :
        self.data = data
        self.next = None

노드의 초기화에 대하여, 해당 노드의 다음 노드는 None(NULL)이 되어야 한다.

다음은 연결 리스트의 구현이다.

# 연결 리스트 구현
class LinkedList :
    def __init__(self, data) :
        self.head = Node(data)

헤더를 처음 노드의 data로 설정한다. 다음은 헤더부터 탐색하여 끝 부분에 노드를 추가하는 코드이다.

# 헤더부터 탐색해 새로운 노드 추가하기
    def append(self, data) :
        current_node = self.head # 현재 노드
        # 현재 노드가 none이 될 때까지 반복
        while current_node.next is not None : 
            current_node = current_node.next
        
        current_node.next = Node(data)

다음은 노드의 순서를 확인하여 해당 노드의 주소를 반환하는 코드이다. 

# 노드 인덱스 알아내서 해당 노드 반환
    def get_node(self, index) :
        cnt = 0
        node = self.head
        while cnt < index :
            cnt += 1
            node = node.next

        return node

다음은 새로운 노드를 기존 노드 사이에 삽입하는 코드이다. 

# 노드 삽입
    def insert_node(self, index, value) :
        new_node = Node(value)
        if index == 0 :
            # 기존의 헤더를 new_node의 다음 노드에 대입
            new_node.next = self.head
            # 헤더는 new_node가 된다.
            self.head = new_node
            return
            
	node = self.get_node(index - 1)
	next_node = node.next
	node.next = new_node
	new_node.next = next_node

다음은 노드를 삭제하는 코드이다.

# 노드 삭제
    def delete_node(self, index) :
        if index == 0 :
            self.head = self.head.next
            return

        node = self.get_node(index - 1)
        node.next = node.next.next

다음은 노드를 탐색하는 코드이다. 탐색하고자 하는 노드를 찾았다면 해당 노드의 데이터를, 찾지 못했다면 None이 반환된다.

# 노드 탐색
    def search_node(self, target) :
        current_node = self.head
        while current_node is not None :
            if current_node.data == target :
                return current_node.data

            current_node = current_node.next

        return None

다음은 노드 전체를 출력하는 코드이다. 모든 노드를 탐색하므로, 시간 복잡도는 O(N)이라 할 수 있겠다. 위의 탐색 코드 또한 마찬가지 !

# 모든 노드 값 출력
    def print_all(self) :
        current_node = self.head
        while current_node is not None :
            print(current_node.data)
            current_node = current_node.next

다음은 실행 예제 코드이다.

# 실행 예제
node = LinkedList(3) # 3 -> None 노드 생성
LinkedList.append(node, 12) # 3 -> 12 -> None
LinkedList.append(node, 8) # 3 -> 12 -> 8 -> None
LinkedList.delete_node(node, 1) # 3 -> 8 -> None
LinkedList.insert_node(node, 1, 12) # 3 -> 12 -> 8 -> None
LinkedList.print_all(node) # 3 12 8 출력
print(LinkedList.search_node(node, 3)) # 3 출력
print(LinkedList.search_node(node, 2)) # None 출력

해당 포스팅은 Singly LinkedList에 대하여 알아보았다. 다음 포스팅은 Doubly LinkedList(이중 연결 리스트)에 대하여 알아보겠다.