LinkedList

1. LinkedList 자료구조란?

LinkedList는 **노드(Node)**들이 연결되어 있는 선형 자료구조입니다.
각 노드는 데이터와 다음 노드에 대한 참조를 가지고 있어, 연결 리스트 형식으로 데이터를 저장합니다.

✔ 배열 vs LinkedList

• 배열은 연속된 메모리 공간에서 데이터를 저장하는 반면, LinkedList는 각각의 노드가 메모리 상에서 떨어져 있으며 다음 노드의 위치를 참조로 연결하여 데이터를 저장합니다.

2. LinkedList의 기본 구조

2.1 노드(Node) 구조

LinkedList는 각 노드가 두 가지 정보를 갖습니다:

• 데이터(Data): 실제 저장되는 값
• 참조(Reference or Pointer): 다음 노드를 가리키는 포인터

각 노드는 **데이터 + 포인터(다음 노드에 대한 참조)**로 구성됩니다.

2.2 종류

• 단일 연결 리스트(Singly LinkedList): 각 노드는 다음 노드만 참조합니다.
• 이중 연결 리스트(Doubly LinkedList): 각 노드는 이전 노드와 다음 노드를 모두 참조합니다.

2.3 LinkedList의 구성

1. 헤드(Head): 리스트의 첫 번째 노드.
2. 노드(Node): 데이터와 포인터를 갖는 개별 항목.
3. 테일(Tail): 리스트의 마지막 노드 (단일 연결 리스트의 경우 포인터가 null).

3. LinkedList에서 시간 복잡도

단일 연결 리스트(Singly LinkedList)

단일 연결 리스트는 각 노드가 다음 노드만 참조하는 구조입니다. 이 구조에서 맨 뒤 데이터에 접근하려면 반드시 첫 번째 노드부터 순차적으로 탐색해야 합니다.

• 맨 뒤 데이터에 접근할 때:
  • 시간 복잡도: O(n)
  • 이유: 단일 연결 리스트에서는 마지막 노드를 찾기 위해 첫 번째 노드부터 시작하여 끝까지 순차적으로 하나씩 따라가야 하므로 시간이 **O(n)**이 걸립니다. 마지막 노드까지 가기 위해서는 전체 리스트를 순차적으로 탐색해야 하기 때문입니다.
• 맨 뒤에 데이터 삽입/삭제:
  • 삽입: O(n) (단, 끝 노드까지 탐색해야 함)
  • 삭제: O(n) (삭제할 노드를 찾고 참조를 갱신해야 하기 때문)
• 맨 앞에서 접근시: O(1)
• 중간 삽입시 : O(n)

이중 연결 리스트(Doubly LinkedList)

이중 연결 리스트는 각 노드가 이전 노드와 다음 노드 모두를 참조하는 구조입니다. 이 덕분에 양방향 탐색이 가능합니다.

• 맨 뒤 데이터에 접근할 때:
  • 시간 복잡도: O(1)
  • 이유: 이중 연결 리스트는 각 노드가 이전 노드에 대한 참조를 가지고 있기 때문에, 마지막 노드에 접근할 때 끝에서부터 시작할 수 있습니다. 리스트의 끝에 바로 접근할 수 있어 탐색 시간이 **O(1)**로 매우 빠릅니다.
• 맨 뒤에 데이터 삽입/삭제:
  • 삽입: O(1) (끝에 바로 삽입 가능)
  • 삭제: O(1) (끝에서 바로 삭제 가능)
• 맨 앞에서 접근시: O(1)
• 중간 삽입시 : O(n)

 

4. LinkedList의 메모리 구조

LinkedList는 배열과는 다르게 연속된 메모리 공간을 사용하지 않고,
각각의 노드가 독립적인 메모리 공간에 존재하며, 참조로 서로 연결됩니다.

4.1 메모리 구조

1. Heap 메모리: 모든 노드가 Heap에 동적으로 할당됩니다.
2. Stack 메모리: 메서드에서 LinkedList 객체의 참조 변수가 Stack에 저장됩니다.
3. 메서드 영역: LinkedList 클래스의 코드와 정적 변수들.

예시:

• LinkedList 객체가 Heap에 할당되면, 각 노드는 next라는 포인터로 다른 노드를 참조합니다.
• 이때 next는 Heap에 있는 다른 노드를 가리키므로 메모리 주소가 동적으로 할당됩니다.

5. LinkedList의 장점과 단점

5.1 장점

1. 동적 크기: LinkedList는 배열처럼 고정된 크기가 없으므로, 필요에 따라 동적으로 크기가 조정됩니다.
2. 삽입/삭제 효율성: 특정 위치에 삽입/삭제할 때 O(1) 시간이 걸립니다. 단, 위치를 찾는 데 시간이 걸릴 수 있습니다.
3. 중간 삽입/삭제 효율적: 배열과 달리 중간에 데이터를 삽입하거나 삭제할 때, 데이터를 이동할 필요 없이 참조만 변경합니다.

5.2 단점

1. 메모리 낭비: 각 노드마다 데이터를 저장하는 추가적인 포인터를 저장해야 하므로 배열보다 더 많은 메모리 공간을 차지합니다.
2. 순차 접근: O(n) 시간이 걸리므로, 인덱스를 이용한 임의 접근이 불가능하고 선형 탐색만 가능합니다.