Data structure
연결리스트(Linked List)
자라나라나무나무나
2022. 7. 29. 20:26
연결리스트
각 노드가 데이터와 포인터를 가지며, 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조
연결리스트는 여러 노드들이 연결되어 있는 구조입니다.
여기서 노드란, data와 next를 가지고 있는 구조입니다. (Data, Next 가 같이 묶여 있는 것이 Node)
연결 리스트의 구조에서 맨 앞을 Head라고 하고 맨 마지막을 Tail이라고 합니다.
단방향 연결리스트
: 한쪽 방향으로만 연결된 링크드 리스트
자료 생성시, 노드가 생성되고 포인터는 생선된 포인터를 가르킨다.
양방향 or 쌍방향 연결리스트
: 양쪽 방향으로 연결된 쌍방향 링크드 리스트
자료 생성시, 노드가 생성되고 전 노드의 포인터는 생성된 포인터를 가르킨다.
그리고 생성된 노드의 Prev 포인터는 전 노드를 가르킨다.
환형 연결리스트
: 고리의 처음과 끝이 함께 연결되어 있는 링크드 리스트
양방향과 같지만, 마지막 노드의 Next 포인터는 처음을 가리키는 부분이 추가된다.
연결리스트의 쓰임새
이런 연결 리스트는 웹 브라우저의 히스토리를 관리할 때 사용됩니다.
예를들어 브라우저에서 뒤로가기, 앞으로가기를 할 때 히스토리의 방문기록을 가지고 있기 때문에 손쉽게 이동이 가능합니다.
배열과 연결리스트의 차이
| 장점 | 단점 | |
| 배열 | - 랜덤 엑세스가 빠르다 (매우 빠르게 접근 가능) |
- 메모리 사용 비효율적 - 배열 내의 데이터 이동 및 재구성이 어렵다 |
| 연결리스트 | - 동적으로 메모리 사용가능 - 메모리 효율적 사용 - 데이터 재구성 용이 - 대용량 데이터 처리 적합 |
- 특정위치 데이터 검색 할 때 느리다 - 메모리를 추가적으로 사용해야한다 |
참고