[책] 누구나 자료구조와 알고리즘 - 14장 노드 기반 자료 구조

https://product.kyobobook.co.kr/detail/S000001834743

누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고

 

이어지는 장들에서 다룰 자료구조들은 모두 노드(node) 기반이다.

노드란 컴퓨터 메모리 곳곳에 흩어져있는 데이터 조각이다.

노드 기반 자료 구조는 데이터를 조직하고 접근하는 새로운 방법을 제공하는데 성능상 큰 이점이 많다.

 

연결 리스트의 효율성 면에서의 장단점(trade-off)를 알아보고, 성능이 크게 높아지는 상황도 알아 볼 예정이다.

연결 리스트

연결 리스트(linked-list)는 배열과 마찬가지로 항목의 리스트를 표현하는 자료 구조다.

배열과 연결 리스트는 외견상으로는 유사하게 동작하지만 내부적으로 크게 다르다.

출처: https://velog.io/@jeongs/자료구조-연결리스트와-코드-구현

	배열 array	연결 리스트 linked list
정의	컴퓨터 메모리 내의 연속된 셀 그룹	컴퓨터 메모리 전체에 걸쳐 여러 셀(노드)에 퍼져 있다.
접근	헤드 주소를 알고 있어, 인덱스 번호로 각 셀에 바로 접근 가능.	노드에는다음 노드의 메모리 주소(포인터)도 알고있어, 포인터(=링크)로 접근 가능.
값	각 셀에 실제 데이터가 들어있다	두개의 셀을 사용한다. 첫번째 셀에는 실제 데이터, 두번째 셀에는 다음 노드의 메모리 주소(링크)가 들어있다.
단점	배열이 커질수록 연속된 빈 공간을 찾기 어렵다.	데이터가 커질 수록 탐색 성능이 저하된다.

출처: https://gusdnd852.tistory.com/100

연결 리스트의 마지막 노드의 링크에는 null이 들어있다.

첫번째 노드를 헤드(head), 마지막 노드를 테일(tail)이라고 한다.

연결 리스트 구현

자바처럼 연결 리스트가 내장 된 프로그래밍 언어도 있지만, 그렇지 않은 언어가 많다.

연결 리스트는 간단하게 구현 가능하다.

노드의 구현: 데이터와 다음 노드

# 루비로 작성 된 연결 리스트
class Node:
    attr_accessor :data, :next node
    
    def initialize(data)
    	@data = data
    end
end

노드의 연결

node_1 = Node new("")
node_2 = Node new("")
node_3 = Node new("")
node_4 = Node new("")

node_1.next_node = node_2
node_2.next_node = node_3
node_3.next_node = node_4

next_node 메서드가 노드의 링크 역할을 한다.

연결 리스트의 시작

class LinkedList
    attr_accessor :first_node
    
    def initialize(first_node)
    	@first_node = first_node
    end
end

첫 번째 노드와 연결

list = LinkedList.new(node_1)

연결 리스트를 다룰 때는 첫 번째 노드에만 즉시 접근할 수 있다.

읽기

배열에서는 인덱스를 알면 O(1)만에 읽을 수 있다.

연결 리스트는 첫 번째 노드의 메모리 주소만 알기 때문에 원하는 노드에 도달할 때 까지 선형 탐색을 해야 한다.

리스트의 마지막 노드를 읽으려면 노드가 N개 일 때 O(N)이 걸린다.

 

def read(index)
    # 리스트의 첫 번째 노트에서 시작한다.
    current_node = first_node
    current_index = 0
    
    while current_index < index do
    	# 찾고 있는 인덱스에 도착할 때까지 각 노드의 링크를 계속 따라간다.
    	current_node = current_node.next_node
        current_index += 1
    
    	# 리스트의 끝에 도착했다면 찾고 있는 값이 리스트에 없다는 뜻이므로
        # 널을 반환한다.
    	return nil unless current_node
    end
    
    return current_node.data
end

리스트의 네 번째 노드를 읽으려면 노드의 인덱스를 넣어 메서드를 호출한다.

`list.read(3)`

 

검색

검색은 리스트 내의 값을 찾아 그 인덱스를 반환하는 것이다.

배열을 선형탐색할 때와 마찬가지로 리스트도 검색 속도가 O(N)이다.

def index_of(value)
    # 리스트의 첫 번째 노드에서 시작한다.
    current_node = first_node
    current_index = 0
    
    begin
    	# 찾고 있던 데이터를 찾았으면 반환한다.
    	if current_node.data == value
        	return current_index
        end
        
        # 그렇지 않으면 다음 노드로 이동한다.
        current_node = current_node.next_node
        current_index += 1
    end while current_node

	# 데이터를 찾지 못한 채 전체 리스트를 순회했으면 널을 반환한다.
	return nil
end

원하는 값으로 리스트를 검색할 수 있다.

`list.index_of("time")`

검색은 읽기와 비슷하지만 특정 인덱스에서 중지되는 것이 아닌, value를 찾거나 리스트의 맨 마지막에 도달할 때 까지 실행된다는 점이 다르다.

삽입

연결 리스트는 삽입에서 뚜렷한 장점을 보인다.

배열은 특정 위치(인덱스)에 데이터를 삽입할 때, 나머지 데이터를 한 셀씩 오른쪽으로 옮겨야하기 때문에 효율성이 O(N)이었다.

반면 연결 리스트는 삽입하는데 딱 한 단계만 걸린다. (= O(1))

하지만 주의할 점이 있다.

삽입 연산 자체는 O(1)이지만, 리스트의 맨 앞에 삽입하는 것이 아닌 경우, 탐색이 필요하기 때문에 O(N)을 추가해줘야한다.

최선의 시나리오: 리스트의 맨 앞에 넣어 탐색이 필요 없을 때 = O(1)

최악의 시나리오: 리스트의 맨 끝에 넣어 탐색이 필요할 때 = O(N) + O(1) = O(N)

기본 상태

연결 후

배열과 연결 리스트의 상황 별 최선과 최악의 시나리오

시나리오	배열	연결 리스트
앞에 삽입	최악의 경우	최선의 경우
중간에 삽입	평균적인 경우	평균적인 경우
끝에 삽입	최선의 경우	최악의 경우

 

def insert_at_index(index, value)
    # 전달 받은 value로 새 노드를 생성한다.
    new_node = Node.new(value)
    
    # 리스트 앞에 삽입하는 경우
    if index = 0
    	# 새 노드의 링크가 첫 번째 노드를 가리키게 한다.
    	new_node.next_node = first_node
        # 새 노드를 리스트의 첫 노드로 만든다.
        self.first_node = new_node
        return
    # 원하는 값을 찾았으므로 조기 종료.
    end
    
    # 맨 앞이 아닌 다른 위치에 삽입하는 경우
    current_node = first_node
    current_index = 0
    
    # 먼저, 삽입하려는 새 노드의 바로 앞 노드에 접근한다.
    while current_index < (index - 1) do
    	current_node = current_node.next_node
        current_index += 1
    end
    
    # 새 노드의 링크가 다음 노드를 가리키게 한다.
    new_node.next_node = current_node.next_node
    # 새 노드를 가리키도록 앞 노드의 링크를 수정한다.
    current_node.next_node = new_node
end

위 메서드를 사용하기 위해서는 새로운 value와 index를 모두 전달해야 한다.

`list.insert_at_index(1, "purple")`

 

삭제

연결 리스트의 맨 앞에서 삭제가 일어날 경우, head가 두번째 노드를 가리키게 하기만 하면 되기 떄문에 삽입과 마찬가지로 O(1)이 걸린다.

이와 반대로 배열은 첫 번째 원소의 삭제가 일어날 경우 나머지 데이터를 모두 한 셀씩 왼쪽으로 시프트 해야하기 때문에 효율성이 O(N)이다.

연결 리스트의 마지막 노드 삭제 시, 삭제 연산 자체는 O(1)이지만 마지막까지 이동하기 위해 탐색(=O(N))을 해야하기 때문에 O(N)이다.

시나리오	배열	연결 리스트
앞에 삭제	최악의 경우	최선의 경우
중간에 삭제	평균적인 경우	평균적인 경우
끝에 삭제	최선의 경우	최악의 경우

 

기본 상태

연결 끊기

삭제가 일어날 경우, 다른 노드와의 연결 고리를 끊음으로써 리스트에서만 제거할 뿐이지, 메모리에는 그대로 존재하게 된다.

때문에 리스트에서 노드를 삭제하는 효과를 낳는다.

 

이렇게 쓰이지 않는 노드를 관리하는 방법은 프로그래밍 언어마다 다른데,
Java, C#, 일부 스크립트 언어에서는 쓰이지 않는 노드를 자동으로 감지해 "가비지 컬렉트"하고 메모리를 해제한다.
C, C++ 등의 프로그래밍 언어는 수동 메모리 관리를 가정하고 설계되었으나, 쓰레기 수집을 지원하는 구현도 존재한다.
위키백과

def delete_at_index(index)
    # 첫 번째 노드를 삭제하는 경우
    if index == 0
    	# 단순히 현재 두 번째 노드를 첫 번째 노드에 할당한다.
    	self.first_node = first_node.next_node
        return
    end
    
    current_node = first_node
    current_index = 0
    
    # 먼저 삭제하려는 노드의 바로 앞 노드를 찾아 current_node에 할당한다.
    while current_index < (index - 1) do
    	current_node = current_node.next_node
        current_index += 1
    end
    
    # 삭제 하려는 노드의 바로 뒤 노드를 찾는다.
    node_after_deleted_node = current_node.next_node.next_node
    # current_node의 링크가 node_after_deleted_node를 가리키도록 수정한다.
    # 이렇게 하면 삭제하려는 노드가 리스트에서 제외된다.
    current_node.next_node = node_after_deleted_node
end

연결 리스트의 연산의 효율성

연결 리스트와 배열을 분석해서 비교해 보면 다음 표와 같다.

연산	배열	연결 리스트
읽기	O(1)	O(N)
검색	O(N)	O(N)
삽입	O(N) (끝에서 하면 O(1))	O(N) (앞에서 하면 O(1))
삭제	O(N) (끝에서 하면 O(1))	O(N) (앞에서 하면 O(1))

전체적인 시간 복잡도 면에서 연결 리스트는 그다지 매력적이지 않다.

연결 리스트가 효과적으로 쓰이려면 삽입과 삭제 단계가 O(1)이라는 점을 활용하면 좋다.

 

연결 리스트 다루기

연결 리스트가 빛을 발하는 경우는 한 리스트를 전체 검사해서 많은 원소를 삭제할 때 일어난다.

배열을 이용한다면 삭제되고, 해당 공간을 메꾸기 위해 나머지 데이터들이 셀을 이동하는 과정(O(N))이 추가로 필요하다.

ex) 사용되지 않는 이메일들을 모두 삭제하는 애플리케이션 구현

 

이중 연결 리스트

사실 연결 리스트의 종류는 다양한데, 지금까지 다뤘던 "전형적인" 연결 리스트의 일부를 조금 수정해 연결 리스트를 엄청나게 향상시킬 수 있다.

연결 리스트 변형 중 하나가 이중 연결 리스트(doubly linked list)다.

이중 연결 리스트는 각 노드에 2개의 링크가 있고, 한 링크는 다음 노드를 가리키고, 다른 한 링크는 앞 노드를 가리킨다.

뿐만 아니라 첫 번째 노드 외에 마지막 노드도 항상 기록한다.

이중 연결 리스트

def Node
    attr_accessor :data, :next_node, :previous_node
    
    def initialize(data)
    	@data = data
    end
end

class DoublyLinkedList
    attr_accessor :first_node, :last_node
    
    def initialize(first_node=nil, last_node=nil)
    	@first_node = first_node
        @last_node = last_node
    end
end

리스트의 앞에서 읽기나 삽입, 삭제를 O(1)에 하는 것 처럼, 리스트의 끝에서의 읽기, 삽입, 삭제도 O(1)에 할 수 있다.

이중 연결 리스트 삽입

def insert_at_end(value)
    new_node = Node.new(value)
    
    # 연결 리스트에 아직 원소가 없을 때
    if !first_node
    	@first_node = new node
        @last_node = new node
    else # 연결 리스트에 원소가 하나 이상 있을 때
    	new_node.previous_node = @last_node
        @last_node.next_node = new_node
        @last_node = new_node
    end
end

"전형적인" 연결 리스트는 뒤로만 이동할 수 있지만, 이중 연결 리스트는 앞과 뒤 모두 이동할 수 있어 훨씬 유연하다.

실제로 마지막 노드에서 시작해 첫 번째 노드로 거슬러 올라갈 수도 있다.

이중 연결 리스트 기반 큐

이중 연결 리스트는 리스트 앞과 끝 모두에 바로 접근할 수 있으므로 O(1)에 양 끝에 데이터의 삽입 및 삭제가 가능하다.

이는 큐를 위한 완벽한 내부 자료 구조다.

# 30번째 줄 까지 위의 이중 연결 리스트의 코드 블럭과 동일
class Node
    attr_accessor :data, :next_node, :previous_node
    
    def initialize(data)
    	@data = data
    end
end

class DoublyLinkedList
	attr_accessor :first_node, :last_node
    
    def initialize(first_node=nil, last_node=nil)
    	@first_node = first_node
        @last_node = last_node
    end
    
    def insert_at_node(value)
    	new_node = Node.new(value)
   			
        # 연결 리스트에 아직 원소가 없을 때
        if !first_node
            @first_node = new_node
            @last_node = new_node
        else # 연결 리스트에 노드가 하나 이상 있을 때
            new_node.previous_node = @last_node
            @last_node.next_node = new_node
            @last_node = new_node
        end
    end
    
    def remove_from_front # ✅ 추가 된 함수
    	removed_node = @first_node
        @first_node = @first_node.next_node
        return removed_node
    end
end

class Queue
    attr_accessor :data
    
    def initialize
    	@data = DoublyLinkedList.new
    end
    
    def enque(element)
    	@data.insert_at_end(element)
    end
    
    def deque
    	removed_node = @data.remove_from_front
        return removed_node.data
    end
    
    def read
    	return nil unless @data.first_node
        return @data.first_node.data
    end
end

이중 연결 리스트로 큐를 구현함으로써 삽입과 삭제 모두 O(1)만에 할 수 있게 됐다.

마무리

앞서 봤듯이 배열과 연결 리스트 간 미묘한 차이로 인해 코드가 전에 없이 빨라진다.

연결 리스트를 알아보며 노드 개념도 배웠는데, 이는 가장 단순한 노드 기반 자료 구조다.

이어지는 장들에서는 복잡하고 흥미로운 노드 기반 구조를 배우고, 어떻게 대단한 힘과 효율을 내는지 알아볼 예정이다.