자료구조와 알고리즘 - 연결 리스트

본 내용은 프로그래머스의 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 토대로 작성하였습니다.

1. 연결 리스트란?

• 각 요소를 포인터로 연결하여 관리하는 선형 자료구조
• 각 요소는 노드라고 불리고 데이터 영역과 포인터 영역으로 구성

2. 연결 리스트의 특징

• 메모리가 허용하는한 요소를 제한없이 추가할 수 있음
• 탐색은 O(n)이 소요
• 추가와 삭제가 반복되는 로직에서 사용하면 유용
  • O(1)이 소요
• Singly Linked List, Doubly Linked List, Circular Linked List

3. 배열과 차이점

• 메모리에서의 차이
  • 배열은 순차적으로 요소들을 관리하므로 메모리 영역을 연속적으로 사용
  • 연결 리스트는 각 데이터가 퍼져 있음
  • 연결 리스트는 퍼져있는 메모리 영역을 알기 위해 포인터를 사용하여 각 영역을 참조
• 요소 삭제, 추가
  • 배열의 요소 삭제 및 추가는 선형시간(O(n)) 소요
  • 연결 리스트의 요소 삭제 및 추가는 상수시간(O(1)) 소요

4. Singly Linked List

• 단일 연결 리스트
• Head에서 Tail까지 단방향으로 이어지는 연결 리스트
• 가장 단순한 형태인 연결 리스트
• 헤드 포인터: 헤드를 가리키는 가장 첫번째 출발점
• Tail은 포인터 영역이 null임

요소 찾기

선형 시간(O(n)) 소요

1. 헤드 포인터에서 시작
2. 다음 요소인 헤드를 찾음
3. 해당 요소가 찾는 요소인지 확인
4. 찾는 요소가 아니라면, 포인터 영역을 통해 다음으로 이동
5. 찾는 요소를 찾을 때까지 반복

요소 추가

상수 시간(O(1)) 소요

1. 추가할 요소의 포인터 영역을 다음에 위치할 요소에 가르키게 만듦
2. 이전에 위치할 요소의 포인터 영역을 추가할 요소를 가르키도록 만듦

• 위 과정은 추가를 하는 것만 해당
• 이전 또는 다음에 위치할 요소를 탐색하는 것은 상기대로 선형 시간이 소요되므로 주의

요소 삭제

상수 시간(O(1)) 소요

1. 삭제할 요소의 이전 요소의 포인터가 삭제할 요소의 다음 요소를 가르키도록 함
2. 삭제할 요소를 메모리 상에서 삭제

6. Doubly Linked List

• 이중 연결 리스트
• 양방향으로 이어지는 연결 리스트
• 포인터가 두개 있음
• 단일 연결 리스트보다 자료구조의 크기가 조금 더 큼

요소 추가

상수 시간(O(1)) 소요

1. 추가할 노드의 다음 노드 포인터에 다음 노드를 가리키도록 함
2. 이전 노드의 다음 노드 포인터에 추가할 노드를 가리키도록 함
3. 다음 노드의 이전 노드 포인터에 추가할 노드를 가리키도록 함
4. 추가할 노드의 이전 노드 포인터에 이전 노드를 가리키도록 함

요소 삭제

상수 시간(O(1)) 소요

1. 이전 노드의 다음 노드 포인터가 삭제할 노드의 다음 노드를 가리키도록 함
2. 다음 노드의 이전 노드 포인터가 삭제할 노드의 이전 노드를 가리키도록 함
3. 삭제할 노드를 메모리에서 삭제

7. Circular Linked List

• 환형 연결 리스트
• Tail이 head로 연결되는 연결 리스트
• 메모리를 절약할 수 있음
• 원형 큐 등을 만들 때 사용
• 중간에서 탐색을 시작하더라도 한 바퀴를 돎

Reference

프로그래머스의 코딩테스트 광탈 방지 A to Z : JavaScript