'추가'와 '삭제'가 반복되는 로직은 어떻게 해야할까요?
- 배열을 공부하면서 '추가'와 '삭제'가 반복되는 로직일경우 시간복잡도 부분에서 좋지 않다고 공부했었습니다.
- 배열 X
- 연결 리스트 O
연결 리스트 개요
정의
- 각 요소를 포인터로 연결하여 관리하는 선형 자료구조입니다.
- 각 요소는 노드라고 부르며 데이터 영역과 포인터 영역으로 구성됩니다.
C 언어의 포인터 개념과 비슷
특징
- 메모리가 허용하는한 요소를 제한없이 추가할 수 있다.
- 탐색은 O(n)이 소요된다.
- 요소를 추가하거나 제거할 때는 O(1)이 소요된다.
- Singly Linked List(단일 연결 리스트), Doubly Linked List(이중 연결 리스트), Circular Linked List(원형 연결 리스트) 가 존재한다.
배열과 차이점
배열
- 메모리 순차적으로 사용합니다.
- 배열 요소 추가, 삭제에 O(n) 소요
연결 리스트
- 메모리가 순차적이지 않고 퍼져 있습니다.
- 포인터 사용 각 영역 참조
- 연결 리스트의 노드 추가, 삭제에 O(1) 소요
단일 연결 리스트
정의
- Head 에서 Tail 까지 단방향으로 이어지는 연결 리스트입니다.
- 가장 단순한 형태인 연결 리스트입니다.
핵심 로직
노드 찾기
- 헤드포인터에서 순서대로 탐색, O(n)
노드 추가
- 추가할 노드의 포인터 영역이 다음에 위치할 리스트의 데이터 영역 가리키고, 이전 노드의 포인터 영역이 해당 리스트의 데이터 영역 가리킵니다. O(1)
- 추가를 위한 탐색하지 않도록 주의하여 코드 작성
노드 삭제
- 삭제할 요소 이전 요소의 포인터 영역이 삭제할 요소 다음 요소의 데이터 영역을 가리키고, 삭제할 요소를 삭제합니다. O(1)
이중 연결 리스트
정의
- 양방향으로 이어지는 연결 리스트입니다.
- 노드의 포인터 영역이 양방향으로 두개 있기 때문에 단일 연결 리스트에 비해 자료구조의 크기가 조금 더 큽니다.
- 첫 번째 노드의 이전 노드, 마지막 노드의 다음 노드의 값은 NULL 입니다.
핵심로직
포인터 영역이 하나 더 추가되었을 뿐 시간 복잡도나 알고리즘은 동일합니다.
원형 연결 리스트
정의
- 단일, 이중 연결 리스트에서 마지막 노드오 첫 노드가 연결됩니다.
- 중간에서 탐색을 시작하더라도 한 바퀴를 탐색할 수 있습니다.
핵심로직
단일, 이중 연결 리스트와 동일합니다.
연결리스트의 JS 코드
깃허브 : https://github.com/HyeonWooGa/algorhithm-code-snippet
Aim for the TOP, Developer