CS/자료구조
[알고리즘 스터디 with 케이시] 선형 리스트 - 연결 리스트
Damagucci-juice
2022. 7. 22. 15:18
- 추가와 삭제가 빈번한 자료구조는 연결리스트를 추천한다.
- 배열은 탐색이 빈번한 경우
정의 - 연결 리스트
- 연결 리스트는 각 요소를 포인터로 연결하여 관리하는 선형 자료구조다.
- 각 요소는 노드라고 부르며 데이터 영역과 포인터 영역으로 구성된다.
- 첫번째 노드는 HEAD라고 부른다.
특징
- 메모리가 허용하는 한 요소를 제한없이 추가할 수 있다.
- 탐색은 O(n)이 소요된다.
- 요소를 추가하거나 제거할 때는 O(1)이 소요된다.
- 종류
- Singly Linked List
- Doubly Linked List
- Circular Linked List
배열과 차이점
메모리 차이
- 배열 - 연속적인 메모리 영역 사용
- 연결 리스트 - 각 영역이 떨어져 있고 이를 참조하기 위해 포인터 사용
요소 추가 & 삭제
- 배열 - 선형 시간 O(N)
- 연결 리스트 - O(1)
연결리스트 요소 삭제
순서
- 지우고자 하는 노드를 선택 (A)
- A 이전 노드의 다음 노드를 A.next로 선택
- A = nil
연결 리스트 요소 추가
순서
- 삽입하고자 하는 인덱스 의 노드 지정 A
- 새로운 노드 생성 N
- 새로운 노드 N의 다음 노드를 A로 지정
- Index - 1 의 노드 P의 다음 노드를 N으로 지정
단일 연결 리스트
- 헤드에서 테일까지 단방향
- 가장 단순한 형태의 연결 리스트
요소 찾기
O(N)이 걸린다.
아래는 JS 코드긴 한데, 이해가 어렵지는 않은 코드여서 공유합니다.
이중 연결 리스트
- 양방향으로 이어지는 연결 리스트
- 단일 연결 리스트보다 조금 더 구조가 크다.
- 다음 포인터가 있는것과 비슷하게 이전 노드 포인터가 있다.
환형 링크드 리스트
테일의 포인터가 헤드를 가리키고 있다는 점만 뺴고 싱글과 더블 링크드 리스트와 비슷함.