Chapter 14. 노드 기반 자료 구조

♧ Self-study/<누구나 자료구조와 알고리즘>

Chapter 14. 노드 기반 자료 구조

Grit_0913 2024. 9. 14. 05:17

Chapter 14. 노드 기반 자료 구조

하단의 목차를 클릭하여 이동할 수 있습니다 :)

1. 연결 리스트
2. 연결 리스트 구현 (python)
2-1. 읽기
2-2. 검색
2-3. 삽입
2-4. 삭제
2-5. 연결 리스트의 연산의 효율성
3. 이중 연결 리스트
4. 이중 연결 리스트 기반 큐
5. 연습 문제 정리
6. 이쯤에서 전체 복습

노드란 자료 구조의 일종으로 컴퓨터 메모리 곳곳에 흩어져 있는 자료 구조를 의미한다.

1. 연결 리스트

연결 리스트(linked list)란 배열과 마찬가지로 항목의 리스트를 표현하는 자료 구조이다.
연결 리스트는 컴퓨터 메모리 전체에 걸쳐 데이터가 분산 저장되어 있다. 즉, 배열처럼 연속된 메모리 블록에 데이터가 저장되지 않는다.
연결 리스트에서 컴퓨터 메모리 곳곳에 분산되어 연결된 데이터를 노드(node)라 한다. 연결 리스트는 개별 노드들이 연결된 리스트를 의미한다.
연결 방법
- 노드는 데이터와 링크로 이루어진다.
  - 링크(link)란 현제 노드와 연결되는 다음 노드의 주소이다.
- '데이터 + 링크'로 이루어지기에 4 개의 데이터를 저장할 때 8 개의 셀(데이터 + 링크)을 사용한다.
- 마지막 노드는 다음 노드가 존재하지 않기 때문에 링크에 null을 갖는다.
연결 리스트는 첫 번째 노드는 헤드(head), 마지막 노드를 테일(tail)이라고도 부른다.
배열은 연속된 셀을 사용하지만 연결 리스트는 연속된 셀을 사용하지 않아도 된다. 따라서 비교적 효율적인 상황이 존재한다.

2. 연결 리스트 구현 (python)

Node 구현

class Node:
    def __init__(self, data):
        # data 초기화하여 data 값을 저장한다.
        self.data = data
        # 현제는 다음 node가 없기에 None을 초기화 해 둔다.
        self.next_node = None

테스트 할 데이터를 Node 클래스를 통해 입력

node_1 = Node("once")
node_2 = Node("upon")
node_3 = Node("a")
node_4 = Node("time")

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

연결 리스트의 시작 노드를 명시하기 위해 첫 번째 노드를 저장하는 클래스 구현

# 첫 번째 node를 추적하는 역할을 한다.
class LinkedList:
    def __init__(self, first_node):
        # 첫 번째 node를 초기화.
        self.first_node = first_node

주어진 노드 중 첫 번째 노드를 LinkedList 클래스에 입력한다. (연결 리스트가 구현된다).

list = LinkedList(node_1)

연결 리스트의 중요한 특징 중 하나는 첫 번째 노드에만 즉시 접근할 수 있다는 것이다. 이 특징은 이후 내용들에 중요한 정보가 된다.

2-1. 읽기

연결 리스트를 사용할 경우 컴퓨터는 첫 번째 노드의 위치만 바로 알 수 있다. 이는 첫 번째 노드의 주소만을 저장하고 있기 때문이다.
- 예를 덜어 세 번째 노드를 찾는다면 '첫 번째 노드 → 두 번째 노드 → 세 번째 노드' 순으로 찾아야 한다.
따라서 연결 리스트는 최악의 경우 $O(N)$가 걸린다.
- 배열이 읽기에 $O(1)$이 걸리는 것을 감안하면 매우 비효율적이다.
연결 리스트 읽기 코드 구현 (python)

# 노드 구현
class Node:
    def __init__(self, data):
        # data 초기화하여 data 값을 저장한다.
        self.data = data
        # 현제는 다음 node가 없기에 None을 초기화 해 둔다.
        self.next_node = None
        
# 첫 번째 node를 추적하는 역할을 한다.
class LinkedList:
    def __init__(self, first_node):
        # 첫 번째 node를 초기화.
        self.first_node = first_node

# 읽기----------------------------------------------------------------
    def read(self, index):
        # 리스트의 첫 번째 노드에서 시작한다.
        current_node = self.first_node
        current_index = 0
    
        # current_index가 index보다 작다는 것은
        # 아직 찾고자 하는 index에 해당하는 
        # node에 도달하지 못하였음을 의미한다.
        while current_index < index:
            # 찾고 있는 index 까지 노드를 따라간다.
            current_node = current_node.next_node
            current_index += 1
        
            # current_node가 Node이라면 리스트에 찾는 값이 없음을 의미한다.
            # 마지막 노드의 링크가 null(None)이기 떄문.
            if current_node is None:
            return None
    
        # index를 찾았다면 데이터를 반환한다.
        return current_node.data

2-2. 검색

연결 리스트의 검색 속도는 $O(N)$ 이다. 이는 첫 번째 노드에서 시작하여 값을 따라 다음 노드로 순차적으로 검색을 진행하기 때문이다.
- 배열의 선형 검색 또한 $O(N)$이며 연결 리스트와 동일하다.
연결 리스트 검색 코드 구현 (python, 가장 하단의 함수이다).

# 노드 구현
class Node:
    def __init__(self, data):
        # data 초기화하여 data 값을 저장한다.
        self.data = data
        # 현제는 다음 node가 없기에 None을 초기화 해 둔다.
        self.next_node = None
        
# 첫 번째 node를 추적하는 역할을 한다.
class LinkedList:
    def __init__(self, first_node):
        # 첫 번째 node를 초기화.
        self.first_node = first_node

# 읽기------------------------------------------------------------------
    def read(self, index):
        # 리스트의 첫 번째 노드에서 시작한다.
        current_node = self.first_node
        current_index = 0
    
        # current_index가 index보다 작다는 것은
        # 아직 찾고자 하는 index에 해당하는 
        # node에 도달하지 못하였음을 의미한다.
        while current_index < index:
            # 찾고 있는 index 까지 노드를 따라간다.
            current_node = current_node.next_node
            current_index += 1
        
            # current_node가 Node이라면 리스트에 찾는 값이 없음을 의미한다.
            # 마지막 노드의 링크가 null(None)이기 떄문.
            if current_node is None:
            return None
    
        # index를 찾았다면 데이터를 반환한다.
        return current_node.data
        
# 검색------------------------------------------------------------------
    def index_of(self, value):
        # 리스트의 첫 번째 노드에서 시작한다.
        current_node = self.first_node
        current_index = 0
    
        while current_node:
            # 찾고 있던 데이터를 찾았으면 반환한다.
            if current_node.data == value:
                return current_index
        
            # 그렇지 않으면 다음 노드로 이동한다.
            current_node = current_node.next_node
            current_index += 1
    
        # 데이터를 찾지 못한 채 전체 리스트를 순회했으면 None을 반환한다.
        return None

테스트 코드

# 노드 값들 입력
node_1 = Node("once")
node_2 = Node("upon")
node_3 = Node("a")
node_4 = Node("time")

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

# 첫 번째 노드 초기화
first_list = LinkedList(node_1)

# 검색
first_list.index_of("time")

2-3. 삽입

연결 리스트는 삽입 시 $O(1)$이 걸린다.
- 배열의 경우 삽입 시 $O(N)$이 걸린다.
연결 리스트의 삽입
- step 1 : 삽입하려는 데이터 노드를 생성한다.
- step 2 : 삽입하는 노드를 삽입하려는 위치의 앞과 뒤의 노드와 연결한다.
수행 단계 정리
- step 1 : 삽입하려는 노드의 앞 노드를 찾기 위해 검색을 수행한다.
  - 최악의 경우 마지막 노드까지 검색을 수행할 수 있으며 $O(N)$이 된다.
- step 2 : 삽입하려는 노드를 이전 노드의 링크와 연결한다.
  - 연결하는 단계는 링크만 연결하면 되기에 1 개의 단계만 필요로 한다.
요약 : 최악의 경우 'N(검색) + 1(삽입) = N + 1' 단계가 필요하며 $O(N)$이 된다. 그러나 가장 앞 부분에 삽입을 할 경우 검색 단계가 없기에 $O(1)$이 된다.
- 배열의 경우 앞에 삽입을 하면 모든 데이터를 한 셀씩 우측으로 이동시켜야 하기에 연결 리스트보다 비효율적이다.
표로 정리하면 다음과 같다.

시나리오 (빅 오)
앞에 삽입	배열 > 연결 리스트
중간 삽입	배열 ≈ 연결 리스트
끝에 삽입	배열 < 연결 리스트

연결 리스트 삽입 코드 구현 (python, 가장 하단의 함수이다).

# 노드 구현
class Node:
    def __init__(self, data):
        # data 초기화하여 data 값을 저장한다.
        self.data = data
        # 현제는 다음 node가 없기에 None을 초기화 해 둔다.
        self.next_node = None
        
# 첫 번째 node를 추적하는 역할을 한다.
class LinkedList:
    def __init__(self, first_node):
        # 첫 번째 node를 초기화.
        self.first_node = first_node

# 읽기------------------------------------------------------------------
    def read(self, index):
        # 리스트의 첫 번째 노드에서 시작한다.
        current_node = self.first_node
        current_index = 0
    
        # current_index가 index보다 작다는 것은
        # 아직 찾고자 하는 index에 해당하는 
        # node에 도달하지 못하였음을 의미한다.
        while current_index < index:
            # 찾고 있는 index 까지 노드를 따라간다.
            current_node = current_node.next_node
            current_index += 1
        
            # current_node가 Node이라면 리스트에 찾는 값이 없음을 의미한다.
            # 마지막 노드의 링크가 null(None)이기 떄문.
            if current_node is None:
            return None
    
        # index를 찾았다면 데이터를 반환한다.
        return current_node.data
        
# 검색------------------------------------------------------------------
    def index_of(self, value):
        # 리스트의 첫 번째 노드에서 시작한다.
        current_node = self.first_node
        current_index = 0
    
        while current_node:
            # 찾고 있던 데이터를 찾았으면 반환한다.
            if current_node.data == value:
                return current_index
        
            # 그렇지 않으면 다음 노드로 이동한다.
            current_node = current_node.next_node
            current_index += 1
    
        # 데이터를 찾지 못한 채 전체 리스트를 순회했으면 None을 반환한다.
        return None
        
# 삽입-------------------------------------------------------------------
    def insert_at_index(self, index, value):
        # 전달받은 value로 새 노드를 생성한다.
        new_node = Node(value)
    
        # 리스트 앞에 삽입하는 경우
        if index == 0:
            # 새 노드의 링크가 첫 번째 노드를 가리키게 한다.
            new_node.next_node = first_node
            # 새 노드를 리스트의 첫 노드로 만든다.
            self.first_node = new_node
            return
    
        # 앞이 아닌 다른 위치에 삽입하는 경우
        current_node = self.first_node
        current_index = 0
    
        # 먼저, 삽입하려는 새 노드의 바로 앞 노드에 접근한다.
        while current_index < (index - 1):
            current_node = current_node.next_node
            current_index += 1
        
        # 새 노드의 링크가 다음 노드를 가리키게 한다.
        new_node.next_node = current_node.next_node
    
        # 새 노드를 가리키도록 앞 노드의 링크를 수정한다.
        current_node.next_node = new_node

테스트 코드

# 노드 입력
node_1 = Node("yellow")
node_2 = Node("blue")
node_3 = Node("green")
node_4 = Node("red")

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

# 첫 번째 노드 초기화
first_list = LinkedList(node_1)

# 입력 수행
# 3 번 인덱스에 "purple" 삽입
first_list.insert_at_index(3, "purple")

2-4. 삭제

연결 리스트는 리스트의 앞에서 삭제를 할 경우 한 단계만 걸리기에 매우 효율적이다.
- 맨 앞의 데이터를 삭제할 경우 first_node만 두 번째 노드로 변경하면 된다. 따라서 $O(N)$ 이다.
- 반면 배열은 첫 번째 노드를 삭제할 경우 모든 셀을 왼쪽으로 이동시켜야 하기에 $O(N)$ 이다. 즉, 비효율적이다.
중간에서 삭제하는 경우
- step 1 : 삭제하려는 노드의 바로 앞 노드를 검색한다.
- step 2 : 검색한 노드(삭제 바로 앞)의 링크를 삭제되는 노드에서 분리한 다음 다음 링크와 연결한다.
  - 연결만 바꿔주면 되기에 실제 수행은 한 단계이다. (분리 + 연결이 아님).
연결 리스트의 삭제는 정확히는 노드를 삭제하는 것이 아니다. 연결을 끊는 것이기에 연결이 끊어진 노드(삭제된 노드)는 메모리에 그대로 존재한다. (즉, 삭제하는 효과만 있다).
- 이 경우 가용되지 않는 메모리(노드)를 삭제할 수 있다. 파이썬에서는 '가비지 컬렉트'라고 하며 사용되지 않는 객체들을 메모리에 실제로 삭제한다.
표로 정리하면 다음과 같다.

시나리오 (빅 오)
앞에서 삭제	배열 < 연결 리스트
중간에서 삭제	배열 ≈ 연결 리스트
끝에서 삭제	배열 > 연결 리스트

연결 리스트 삭제 코드 구현 (python, 가장 하단의 함수이다).

# 노드 구현
class Node:
    def __init__(self, data):
        # data 초기화하여 data 값을 저장한다.
        self.data = data
        # 현제는 다음 node가 없기에 None을 초기화 해 둔다.
        self.next_node = None
        
# 첫 번째 node를 추적하는 역할을 한다.
class LinkedList:
    def __init__(self, first_node):
        # 첫 번째 node를 초기화.
        self.first_node = first_node

# 읽기----------------------------------------------------------------------
    def read(self, index):
        # 리스트의 첫 번째 노드에서 시작한다.
        current_node = self.first_node
        current_index = 0
    
        # current_index가 index보다 작다는 것은
        # 아직 찾고자 하는 index에 해당하는 
        # node에 도달하지 못하였음을 의미한다.
        while current_index < index:
            # 찾고 있는 index 까지 노드를 따라간다.
            current_node = current_node.next_node
            current_index += 1
        
            # current_node가 Node이라면 리스트에 찾는 값이 없음을 의미한다.
            # 마지막 노드의 링크가 null(None)이기 떄문.
            if current_node is None:
            	return None
    
        # index를 찾았다면 데이터를 반환한다.
        return current_node.data
        
# 검색----------------------------------------------------------------------
    def index_of(self, value):
        # 리스트의 첫 번째 노드에서 시작한다.
        current_node = self.first_node
        current_index = 0
    
        while current_node:
            # 찾고 있던 데이터를 찾았으면 반환한다.
            if current_node.data == value:
                return current_index
        
            # 그렇지 않으면 다음 노드로 이동한다.
            current_node = current_node.next_node
            current_index += 1
    
        # 데이터를 찾지 못한 채 전체 리스트를 순회했으면 None을 반환한다.
        return None
        
# 삽입----------------------------------------------------------------------
    def insert_at_index(self, index, value):
        # 전달받은 value로 새 노드를 생성한다.
        new_node = Node(value)
    
        # 리스트 앞에 삽입하는 경우
        if index == 0:
            # 새 노드의 링크가 첫 번째 노드를 가리키게 한다.
            new_node.next_node = first_node
            # 새 노드를 리스트의 첫 노드로 만든다.
            self.first_node = new_node
            return
    
        # 앞이 아닌 다른 위치에 삽입하는 경우
        current_node = self.first_node
        current_index = 0
    
        # 먼저, 삽입하려는 새 노드의 바로 앞 노드에 접근한다.
        while current_index < (index - 1):
            current_node = current_node.next_node
            current_index += 1
        
        # 새 노드의 링크가 다음 노드를 가리키게 한다.
        new_node.next_node = current_node.next_node
    
        # 새 노드를 가리키도록 앞 노드의 링크를 수정한다.
        current_node.next_node = new_node
        
# 삭제---------------------------------------------------------------------
    def delete_at_index(self, index):
        # 첫 번째 노드를 삭제하는 경우
        if index == 0:
            # 단순히 현재 두 번째 노드를 첫 번째 노드에 할당한다.
            self.first_node = first_node.next_node
            return
    
        current_node = self.first_node
        current_index = 0
    
        # 먼저 삭제하려는 노드의 바로 앞 노드를 찾아 current_node에 할당
        while current_index < (index - 1):
            current_node = current_node.next_node
            current_index += 1
    
        # 삭제하려는 노드의 바로 뒤 노드를 찾는다.
        node_after_deleted_node = current_node.next_node.next_node
    
        # current_node의 링크가 node_after_deleted_node를 가리키도록 수정
        # 이렇게 하면 삭제하려는 노드가 리스트에서 제외된다.
        current_node.next_node = node_after_deleted_node

테스트 코드

# 노드 입력
node_1 = Node("yellow")
node_2 = Node("blue")
node_3 = Node("green")
node_4 = Node("red")

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

# 첫 번째 노드 초기화
first_list = LinkedList(node_1)

# 삭제 수행
first_list.delete_at_index(3)

2-5. 연결 리스트의 연산의 효율성

3. 이중 연결 리스트

이중 연결 리스트(doubly linked list)란 뒤의 노드 뿐만아니라 앞의 노드와도 링크로 연결된 연결 리스트를 의미한다.
- 이중 연결 리스트는 앞 노드와도 연결되기에 기존 연결 리스트 보다 효율적이다. 즉 몇 작업들이 $O(1)$로 변한다.
이중 연결 리스트에서 하나의 노드는 세 개의 셀을 사용한다.
- 첫 번째 셀 : 앞 노드와의 링크이다. 이전 노드의 값을 가리킨다.
  - 첫 번째 노드의 경우 이전 노드가 없기에 null을 갖는다.
- 두 번째 셀 : 해당 노드의 값을 저장한다.
- 세 번째 셀 : 다음 노드로의 링크이다. 이후 노드의 값을 가리킨다. (일반 연결 리스트와 동일).
  - 마지막 노드의 경우 이후 노드가 없기 때문에 null을 갖는다.
이중 연결 리스트는 노드가 앞과 뒤 모두 연결되기에 앞과 뒤로 모두 이동할 수 있다. 반면 일반적인 연결 리스트는 앞으로만 이동이 가능하다.
교재의 이중 연결 리스트에 삽입 메서드 정의 코드 변환 (python)

class Node:
    def __init__(self, data):
        self.data = data
        self.next_node = None
        self.previous_node = None

class DoublyLinkedList:
    def __init__(self, first_node=None, last_node=None):
        self.first_node = first_node
        self.last_node = last_node

# 이중 연결 리스트 삽입 구현-----------------------------------
    def insert_at_end(self, value):
        new_node = Node(value)
        
        # 연결 리스트에 아직 원소가 없을 때
        if self.first_node is None:
            self.first_node = new_node
            self.last_node = new_node
        else: # 연결 리스트에 원소가 하나 이상 있을 때
		        # new_node의 앞 링크에 연결
            new_node.previous_node = self.last_node
            # last_node 뒤의 링크에 new_node 연결
            self.last_node.next_node = new_node
            # new_node를 last_node로 초기화
            self.last_node = new_node

4. 이중 연결 리스크 기반 큐

이중 연결 리스트는 리스트의 앞과 뒤의 끝 지점에서 데이터를 삽입할 때 O(1), 삭제할 때도 O(1)이 걸린다.
- 큐는 FIFO로 처음 들어온 값이 처음 나간다.
이중 연결 리스트를 큐의 자료 구조로 사용하여 구현할 수 있다.
- 이유는 이중 연결 리스트가 삽입과 삭제에 $O(1)$이 걸리기 때문에 큐의 FIFO를 구현할 수 있기 때문이다.
- 큐는 FIFO로 자료 구조 상 첫 삽입이 $O(1)$이고, 첫 삭제도 $O(1)$이다.
- 배열은 끝 삽입의 경우 $O(1)$이지만 삭제의 경우 모든 데이터를 왼쪽으로 옮겨야 하기에 $O(N)$이다. 따라서 큐에 적합하지 않다.
이중 연결 리스트를 자료 구조로 하는 큐 구현 (python)
- 삽입과 삭제 모두 O(1)이다.

class Node:
    def __init__(self, data):
        self.data = data
        self.next_node = None
        self.previous_node = None

class DoublyLinkedList:
    def __init__(self, first_node=None, last_node=None):
        self.first_node = first_node
        self.last_node = last_node
    
    def insert_at_end(self, value):
        new_node = Node(value)
        
        # 연결 리스트에 아직 원소가 없을 때
        if not self.first_node:
            self.first_node = new_node
            self.last_node = new_node
        else: # 연결 리스트에 노드가 하나 이상 있을 때
            new_node.previous_node = self.last_node
            self.last_node.next_node = new_node
            self.last_node = new_node
    
    # 이중 연결 리스트에 메서드 연결
    def remove_from_front(self):
        removed_node = self.first_node
        self.first_node = self.first_node.next_node
        return removed_node

# 큐 클래스 구현-----------------------------------------
class Queue:
    def __init__(self):
        self.data = DoublyLinkedList()
    
    def enqueue(self, element):
        self.data.insert_at_end(element)
    
    def dequeue(self):
        removed_node = self.data.remove_from_front()
        return removed_node.data
    
    def read(self):
        if not self.data.first_node:
            return None
        else:
            return self.data.first_node.data

5. 연습 문제 정리

1 번

class Node:
    def __init__(self, data=None, next_node=None):
        self.data = data
        self.next_node = next_node

class LinkedList:
    def __init__(self):
        self.first_node = None

    def print(self):
        # 현제 노드로 첫 번째 노드를 받는다.
        current_node = self.first_node
        
        # 현제 노드가 비어있지 않다면 
        # 출력을 반복한다.
        while current_node is not None:
            print(current_node.data)
            current_node = current_node.next_node

# 링크드 리스트와 노드 생성 및 테스트
linked_list = LinkedList()

# 노드 생성
node1 = Node(data=1)
node2 = Node(data=2)
node3 = Node(data=3)

# 노드 연결
linked_list.first_node = node1
node1.next_node = node2
node2.next_node = node3

# 링크드 리스트의 데이터 출력
linked_list.print()

2 번

class Node:
    def __init__(self, data):
        self.data = data
        self.next_node = None
        self.previous_node = None

class DoublyLinkedList:
    def __init__(self):
        self.first_node = None
        self.last_node = None
        
    def print_in_reverse(self):
        current_node = self.last_node
        while current_node is not None:
            print(current_node.data)
            current_node = current_node.previous_node

# 노드 생성
node1 = Node(data=1)
node2 = Node(data=2)
node3 = Node(data=3)

# 노드 연결
node1.next_node = node2
node2.previous_node = node1
node2.next_node = node3
node3.previous_node = node2

# DoublyLinkedList의 first_node와 last_node 설정
doubly_linked_list.first_node = node1
doubly_linked_list.last_node = node3

# 링크드 리스트의 데이터 출력
doubly_linked_list.print_in_reverse()

Class에서는 개별 노드의 연결 구조만 작성되어 있다. 따라서 수행 단계에서 각 노드들에 값을 주어 노드 연결을 해야한다.

3 번

# 노드 구현
class Node:
    def __init__(self, data):
        # data 초기화하여 data 값을 저장한다.
        self.data = data
        # 현제는 다음 node가 없기에 None을 초기화 해 둔다.
        self.next_node = None
        
# 첫 번째 node를 추적하는 역할을 한다.
class LinkedList:
    def __init__(self, first_node):
        # 첫 번째 node를 초기화.
        self.first_node = first_node
        
    def last(self):
        current_node = self.first_node
        
        # current_node의 다음 노드가 null일 때 까지 반복
        # 다시 말하면
        # 반복이 끝나면 해당 노드가 마지막 노드이다.
        while current_node.next_node:
            current_node = current_node.next_node
    
        return current_node.data

# 노드 생성
node1 = Node(data=1)
node2 = Node(data=2)
node3 = Node(data=3)

# 노드 연결
node1.next_node = node2
node2.next_node = node3

# 링크드 리스트 생성 및 첫 번째 노드 설정
linked_list = LinkedList(first_node=node1)

# 링크드 리스트의 마지막 데이터 출력
print(linked_list.last())  # Output: 3

4 번

# 노드 구현
class Node:
    def __init__(self, data):
        # data 초기화하여 data 값을 저장한다.
        self.data = data
        # 현제는 다음 node가 없기에 None을 초기화 해 둔다.
        self.next_node = None
        
# 첫 번째 node를 추적하는 역할을 한다.
class LinkedList:
    def __init__(self, first_node):
        # 첫 번째 node를 초기화.
        self.first_node = first_node
        
    def reverse(self):
        previous_node = None
        current_node = self.first_node
        
        while current_node:
            next_node = current_node.next_node
            
            current_node.next_node = previous_node
            
            previous_node = current_node
            current_node = next_node
        
        self.first_node = previous_node

해당 코드는 단순히 정답을 python으로 변환한 것이다. 어떤 로직을 따라가는지는 교재에 자세히 설명되어 있다.

5 번

def delete_middle_node(node):
    # 삭제할 노드에 해당 노드의 다음 노드 값을 받는다.
    node.data = node.next_node.data
    
    # 삭제할 노드의 다음 노드를 해당 노드의 다음 다음 노드로 연결한다.
    node.next_node = node.next_node.next_node

해당 문제의 풀이 또한 책에 자세히 나와있다.
중요한 점은 다음과 같다.
- 연결 리스트는 앞의 노드에 접근이 불가하다. 따라서 삭제할 때 삭제 대상이 되는 노드의 이전 노드에 접근할 수 없다면 삭제가 불가능하다 생각할 수 있다.
- 그러나 삭제할 노드와, 삭제할 노드의 다음 노드, 그리고 삭제할 노드의 다음 다음 노드, 즉 세 개의 노드를 통해 노드 삭제를 진행할 수 있다.

6. 이쯤에서 전체 복습

공부를 하다보면 점점 숲을 보기보다 나무에 집중하게 되는 듯하다. 중간에 큰 그림을 다시 환기하면 공부의 목적과 방향성을 잃는 것을 방지한다. 다음은 한빛출판네트워크의 자료이다. 책의 중반부쯤 온 지금 복습을 한 번해두면 좋을 듯하여 첨부한다.

https://www.hanbit.co.kr/channel/category/category_view.html?cms_code=CMS8073601837

개발자는 반드시 자료구조와 알고리즘을 배워야 할까?

'프로그래머라면 반드시 알고리즘을 배워야 하나요?' 언젠가부터 개발자 채용 과정에서 코딩 테스트를 보는 기업이 늘어나자 이런 질문이 줄어들었습니다. 알고리즘이 취업과 직결된 이후 알고

www.hanbit.co.kr

'♧ Self-study > <누구나 자료구조와 알고리즘>' 카테고리의 다른 글

Chapter 16. 힙으로 우선순위 유지하기 (0)	2024.09.19
Chapter 15. 이진 탐색 트리로 속도 향상 (2)	2024.09.17
Chapter 13. 속도를 높이는 재귀 알고리즘 (9)	2024.09.11
Chapter 12. 동적 프로그래밍 (0)	2024.09.10
Chapter 11. 재귀적으로 작성하는 법 (0)	2024.09.09

현재글Chapter 14. 노드 기반 자료 구조

Grit

Grit 입니다.

SUM, 태블로 (Tableau), concat, subquery, 통계 검정 (statistical test), 경영정보시각화, SQL 코딩테스트, Round, AVG, date, Limit, 자료 구조 알고리즘 (ds & algo), GROUP BY, INNER JOIN, year, 회귀분석 (regression), Having, like, 머신러닝 (machine learning), split(), order by, CASE WHEN, 알고리즘, 프로그래머스 알고리즘, date_format, count, SELF JOIN, where, TIMESTAMPDIFF, R,

Today :
Yesterday :

Grit

Chapter 14. 노드 기반 자료 구조

Chapter 14. 노드 기반 자료 구조

1. 연결 리스트

2. 연결 리스트 구현 (python)

3. 이중 연결 리스트

4. 이중 연결 리스크 기반 큐

5. 연습 문제 정리

6. 이쯤에서 전체 복습

'♧ Self-study > <누구나 자료구조와 알고리즘>' 카테고리의 다른 글

'♧ Self-study/<누구나 자료구조와 알고리즘>'의 다른글

티스토리툴바

« 2025/06 »
일	월	화	수	목	금	토
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

Chapter 14. 노드 기반 자료 구조

Chapter 14. 노드 기반 자료 구조

1. 연결 리스트

2. 연결 리스트 구현 (python)

3. 이중 연결 리스트

4. 이중 연결 리스크 기반 큐

5. 연습 문제 정리

6. 이쯤에서 전체 복습

'♧ Self-study > <누구나 자료구조와 알고리즘>' 카테고리의 다른 글

'♧ Self-study/<누구나 자료구조와 알고리즘>'의 다른글

관련글

티스토리툴바