14장 노드 기반 자료구조

• 노드Node: 컴퓨터 메모리 곳곳에 흩어져 있는 데이터 조각
• 노드 기반 자료구조는 데이터를 조직하고 접근하는 새로운 방법을 제공하는데 성능상 큰 이점이 많다.
• 14장에서는 가장 간단한 노드 기반 자료구조인 연결 리스트를 살펴본다.

1. 연결 리스트

• 연결 리스트Linked List는 배열과 마찬가지로 항목의 리스트를 표현하는 자료 구조다.
• 컴퓨터에 들어 있는 메모리는 데이터조각을 저장하는 셀들의 거대한 집합으로 나타낼 수 있다.
• 코드에서 배열을 생성하면 메모리 내에 연속된 빈 셀 그룹을 찾아 데이터를 저장할 수 있도록 할당한다.
• 컴퓨터는 어떤 메모리 주소든 한 번에 접근할 수 있으므로 배열 내 어떤 인덱스든 바로 갈 수 있다.
• 그러나 연결 리스트 내 데이터는 연속된 메모리 블록이 아니라 컴퓨터 메모리 전체에 걸쳐 여러 셀에 퍼져 있을 수 있다.
• 메모리 곳곳에 흩어진 연결된 데이터를 노드라고 부른다.
• 연결 리스트에서 각 노드는 리스트 내 한 항목을 나타낸다.
• 각 노드는 약간의 추가 정보, 즉 연결 리스트 내에 다음 노드의 메모리 주소도 포함한다.
• 이 추가 데이터, 즉 다음 노드의 메모리 주소로의 포인터를 링크라고 부른다.
• 데이터가 컴퓨터 메모리 전체에 흩어질 수 있다는 점에서 연결 리스트가 배열보다 유리할 수 있다.

2. 연결 리스트 구현

• Java처럼 연결 리스트가 내장된 프로그래밍 언어도 있다.
• 그러나 없는 언어도 많고 생각보다 쉽게 구현할 수 있다.
• 연결 리스트를 다룰 때는 첫 번째 노드에만 즉시 접근할 수 있다.

3. 읽기

• 컴퓨터는 O(1)시간에 배열에서 값을 읽을 수 있다.
• 프로그램은 연결 리스트의 첫 번째 노드의 메모리 주소만 알고, 나머지 노드가 어디에 있는지 바로 알지 못한다.
• 리스트의 마지막 노드를 읽으려면 리스트의 노드가 N개일 때 O(N)시간이 필요하다.

4. 검색

• 배열의 검색은 O(N)이다.
• 연결 리스트의 검색 또한 O(N)이다.

5. 삽입

• 연결 리스트가 배열에 비해 뚜렷한 장점을 보일 수 있는 연산이 바로 삽입이다.
• 배열 삽입에서 최악의 시나리오는 프로그램이 인덱스 0에 데이터를 삽입할 때다. 이때의 효율성은 O(N)이다.
• 그러나 연결 리스트의 삽입 효율성은 O(1)이다.

6. 삭제

• 연결 리스트는 삭제도 매우 빠른데, 특히 리스트 앞에서 삭제할 때 빠르다.
• 연결 리스트에서 노드를 삭제하려면 다른 노드와의 연결고리를 끊으면 된다.
• 연결 리스트에서 다른 노드와의 연결고리를 끊는 것으로 리스트에서 제거하면, 그 노드의 정보는 메모리 어딘가에 계속 존재하지만 더 이상 정확한 메모리 주소를 모르는 상태가 된다.
• 이렇게 삭제된 노드를 처리하는 방식은 프로그래밍 언어마다 다르다. Java에서는 쓰이지 않는 노드를 자동으로 감지하여 Garbage Collector가 처리하여 메모리를 해제한다.

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

• 배열과 연결 리스트를 비교해 보자.
• 검색과 삽입, 삭제는 배열과 비슷하고 읽기는 훨씬 느리다.
• 그러나 연결 리스트의 장점은 다음과 같다: 실제 삽입과 삭제 연산의 효율성이 O(1)에 근사하다.

8. 연결 리스트 다루기

• 연결 리스트가 빛을 발하는 경우는 한 리스트를 검사해서 많은 원소를 삭제할 때다.
• 연결 리스트는 삽입이나 삭제 시 다른 데이터의 위치를 옮기지 않아도 되므로 전체 리스트를 훑으며 삽입이나 삭제를 수행하기에 매우 알맞은 자료구조다.

9. 이중 연결 리스트

• 연결 리스트의 변형 중 하나가 이중 연결 리스트이다.
• 노드 자신의 다음 노드만 가리켰던 기존의 연결 리스트와 다르게, 이중 연결 리스트의 노드는 노드 자신의 이전 노드도 가리킨다.
• 이를 통해 리스트 앞과 뒤로 모두 이동할 수 있어 훨씬 유연하다.

10. 이중 연결 리스트 기반 큐

• 이중 연결 리스트는 리스트 앞과 끝 모두에 접근할 수 있으므로 O(1) 시간에 양 끝 데이터를 삽입&삭제할 수 있다.
• 그렇기 때문에 이중 연결 리스트는 큐를 위한 완벽한 내부 자료구조다.

11. 마무리

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