연결 리스트 시간복잡도
2023. 7. 17. 15:26ㆍ자바스크립트 정리
728x90
연결리스트
연결리스트는 각 요소를 포인터로 연결하여 관리하는 선형 자료구조다
각 요소는 노드라고 부르며 데이터 영역과 포인터 영역으로 구성된다
연결리스트의 특징은
▶메모리가 허용하는 한 요쇼를 제한없이 추가할 수 있다.
▶탐색은0(n)이 소요된다.
▶요소를 추가하거나 제거할 때는 0(1)이 소요된다.
▶Singly Linked List, Doubly Linked List, Circular Linked List가 존재한다.
배열과 차이점
메모리 차이
배열 요소 삭제
배열 요소 삭제
연결 리스트 요소 삭제
연결 리스트 요소 추가
Singly Linked List
Head에서 Tail까지 단방향으로 이어지는 연결 리스트 가장 단순한 형태의 연결 리스트다.
요소 찾기
요소 추가
요소 삭제
Doubly Linked List
양방향으로 이어지는 연결 리스트
Singly Linked List 보다 자료구조의 크기가 조금 더 크다.
요소추가
요소 삭제
Circular Linked List
Singly 혹은 Doublt Linked List 에서 Tail이 Head로 연결되는 연결 리스트 메모리를 아껴쓸 수 있다.
원형 큐등을 만들때 사용된다.
'자바스크립트 정리' 카테고리의 다른 글
| 자료구조 & 알고리즘 (큐-Queue) (0) | 2023.07.18 |
|---|---|
| 자료구조&알고리즘 (스택) (0) | 2023.07.18 |
| 시간 복잡도 배열 (0) | 2023.07.17 |
| DOM (0) | 2023.07.17 |
| 쿠키(Cookie) (0) | 2023.07.17 |