연결리스트란?
연결리스트의 기본구조
- Node: 데이터 + 다음 데이터를 가리키는 주소. 기본 단위
- Pointer: 각 노드에서 다음 데이터를 가리키는 주소값을 저장
- Head: 시작점의 데이터
- Tail: 마지막 데이터
- Next: 다음 데이터. 없을 경우 Null값을 가진다.
연결리스트의 특징(C언어에 해당)
장점:
- 미리 데이터 공간을 할당할 필요가 없다.
- 유동적으로 데이터 삽입, 삭제 가능. (가리키는 주소값을 자신으로 하면 됨.)
- 수정 시 시간복잡도 O(1).
단점:
- 각 노드에 별도로 주소 공간을 가져야 함. (저장공간 효율이 떨어짐)
- 데이터를 찾는데 시간이 오래걸림. (하나씩 타고 가야 하기 때문)
단방향 연결리스트
삽입: E라는 노드가 있을 경우, A의 Next값으로 E의 주소를 넣고 E의 Next값으로 B의 주소를 넣으면 됨.
삭제: E라는 노드가 있을 경우, 다시 A의 Next값을 B의 주소값으로 바꾸면 된다. C언어의 경우 E를 사용하지 않는다는 명시를 해줘야 함.
양방향 연결리스트
Next값에 대한 부분은 단방향과 같음.
삽입: E라는 노드가 있을 경우, E의 Prev값을 A의 주소값으로 바꾸고 B의 Prev값을 E의 주소값으로 바꾸면 된다.
삭제: E라는 노드가 있을 경우, 다시 B의 Prev값을 A의 주소값으로 바꾸면 된다.
'Computer Science > 자료구조' 카테고리의 다른 글
| 우선순위 큐(Priority Queue) & 힙(Heap) (0) | 2022.06.17 |
|---|---|
| 트리(Tree) (0) | 2022.06.17 |
| 큐(Queue) (0) | 2022.06.17 |
| 스택(Stack) (0) | 2022.06.17 |
| 배열(Array) (0) | 2022.06.17 |
