단순 연결 리스트 (Simple List)
시작부분에 head가 있으며 노드에 값과 다음 노드를 가리키는 주소값을 가지고 있습니다.
단방향으로 진행되는 리스트를 의미합니다.
장점 : 추가 삭제시 O(1)의 시간복잡도를 가짐
단점 : 배열이나 트리 구조와는 달리 특정 위치 검색시 O(n) 의 시간이 걸림
이중 연결 리스트 (Doubly List)
양방향으로 이동할 수 있는 리스트로
노드에서 다음 노드를 가리키는 주소값과 이전 노드를 가리키는 주소값 두개를 가지고 있습니다.
양방향으로 이동할 수 있다는 장점으로 데이터를 삭제할 때 이전 노드를 찾기위해 한번 더 탐색을 하지 않아도 됩니다.
단순 - (B를 지우기 위해서 B까지 탐색, B이전에 있는 노드를 찾기위해 A를 찾을때까지 탐색, A와 C를 연결)
이중 - (B를 지우기 위해서 B까지 탐색, B이전에 있는 노드로 이동, A와 C를 연결)
단점으로는 메모리를 더 사용한다는 단점이 있습니다.
환형 연결 리스트(Circular List)
단순 연결 리스트와 비슷한 형태로 마지막 노드가 head가 가리키는 처음 노드를 가리켜서
리스트가 원형의 모양을 가진다는 특징이 있습니다.
일반적으로 head가 마지막 노드를 가리키게 구성
head를 tail이라고도 부름
원형 연결리스트 처음 부분에 삽입
1. 새로운 노드를 head가 가리키는 노드가 가리키는곳과 동일하게 설정
2. head가 가리키는 노드를 새로운 노드를 가리키게 설정
원형 연결리스트 끝 부분에 삽입
1. 새로운 노드를 head가 가리키는 노드가 가리키는곳과 동일하게 설정
2. head가 가리키는 노드를 새로운 노드를 가리키게 설정
3. head를 새로운 노드를 가리키게 설정
'자료구조' 카테고리의 다른 글
| 힙 (Heap) (0) | 2021.05.05 |
|---|---|
| 트리 (Tree), 이진 트리 (Binary Tree) (0) | 2021.05.05 |
| 배열(Array), 리스트(List) (0) | 2021.05.03 |
| 동적 메모리 할당, malloc, calloc, realloc (0) | 2021.05.03 |
| 구조체, typedef (0) | 2021.05.03 |