[자료구조/알고리즘] 연결 리스트 (Linked List)

연결 리스트 (Linked List)

 

• 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료구조
• 삽입 및 삭제는 O(1)이 소요되며 탐색에는 O(n)이 소요된다.
• 배열과 달리 연결 리스트 원소들의 주소가 불연속적임.

 

장점

• 배열(Array)과 달리 크기를 동적으로 조절할 수 있어 메모리 관리가 효율적임
• 삽입과 삭제 시 노드의 링크만 바꿔주면 되기 때문에 효율적

 

Q. 배열(Array)의 원소가 삭제될 때는 메모리에서 어떤 일이 일어나나요?
 
A: 사실은 배열에서 원소를 삭제를 한다고 해서 메모리에서 그 공간이 빈 공간으로 남는 것이 아닙니다. 다만, 배열에서 삭제된 원소의 위치를 다른 원소들이 한칸씩 앞으로 이동하면서 채워지게 됩니다. 
삭제된 원소의 메모리 공간은 논리적으로는 비워져 있지만 물리적으로는 여전히 점유한 상태입니다.반면, 연결 리스트에서는
1. 삭제하려는 노드를 찾은 후, 이전 노드와 다음 노드의 링크를 수정하여 삭제된 노드를 연결 리스트에서 완전히 분리시킵니다.
2. 분리된 노드를 메모리에서 해체해버립니다. 이후에 해당 노드가 가지고 있던 메모리 공간을 물리적,논리적으로 비워 다시 사용할 수 있게 됩니다.

그래서 연결 리스트(Linked List)가 배열(Array)보다 메모리 관리에 효율적이란 것입니다.

 

 

단점

• 인덱스를 통해 요소에 접근가능한 배열과 달리 순차적으로 노드를 따라가야 하기 때문에 속도가 느릴 수 있음.
• 각 노드가 데이터 외의 링크를 저장해야 하므로 배열에 비해 추가 메모리 공간이 필요함. 

---

1. 연결 리스트의 구성요소

• 노드(Node): 연결 리스트의 기본 구성 단위, 데이터와 링크로 구성됨.
  • 데이터(Data): 노드가 저장하는 실제 정보
  • 링크(Link): 다음 노드의 주소(참조)를 저장하는 포인터, 이 링크를 통해 노드들이 서로 연결됨
• 헤더(Header): 연결 리스트의 첫 번째 노드를 가리키는 포인터, 연결 리스트의 시작점을 나타내며 이 노드를 통해 리스트의 모든 노드에 접근 가능
• 테일(Tail, 선택적): 연결 리스트의 마지막 노드를 가리키는 포인터, 이 포인터는 이중 연결 리스트과 같은 특정 연결 리스트에서 유용하게 사용 

 

 

2. 연결 리스트의 종류

연결리스트 종류

• 싱글 연결 리스트: next 포인터만 가진다.
• 이중 연결 리스트: next 포인터와 prev 포인터를 가진다.
• 원형 이중 연결 리스트: 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리키고 있다.

 

3. 연결 리스트 코드 구현

1. 노드 클래스 정의

class Node:
    def __init__(self, data=None):
        self.data = data  # 노드가 저장할 데이터
        self.next = None  # 다음 노드를 가리키는 포인터

 

 

2. 연결 리스트 클래스

• LinkedList 클래스를 정의하여 삽입,출력 메서드 정의

class LinkedList:
    def __init__(self):
        self.head = None  # 리스트의 첫 번째 노드를 가리키는 포인터
	
"""리스트의 끝에 새로운 노드를 추가"""
    def append(self, data):
        new_node = Node(data)  # 새 노드 생성
        if self.head is None:
            self.head = new_node  # 리스트가 비어있으면 새 노드를 헤드로 설정
            return
        
        current = self.head
        while current.next:  # 리스트의 끝까지 이동
            current = current.next
        current.next = new_node  # 리스트의 끝에 새 노드 추가

"""리스트의 모든 노드를 출력"""
    def display(self):    
        current = self.head
        while current:
            print(current.data, end=' -> ')
            current = current.next
        print('None')