soowanlog
Linked List 본문
- Linked List(연결 리스트)란?
연결 리스트란 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 저장하는 자료구조입니다.
데이터를 가지고 있는 노드들은 서로 연결되어 있는데 포인터가 다음이나 이전 노드와 연결하는 역할을 합니다.
- Linked List(연결 리스트)의 종류
- Singly Linked List(단일 연결 리스트) :
각 노드가 데이터와 포인터 한 개로 구성되고, 각 노드의 포인터는 다음 노드를 가리킵니다.
맨 처음 노드를 가리키는 헤드 포인터가 있습니다.
마지막 노드의 포인터는 보통 NULL입니다.
- Doubly Linked List(이중 연결 리스트) :
단일 연결 리스트와 달리 각 노드가 데이터와 포인터 두 개로 구성되고, 각각의 포인터는 이전과 다음 노드를 가리킵니다.
이로 인해 삽입과 삭제가 더욱 효율적으로 이루어지지만 메모리 공간을 더 사용해야 하는 단점이 있습니다.
- Linked List(연결 리스트)의 장점
- 빠른 삽입과 삭제 :
연결 리스트는 삽입과 삭제 시에 포인터만 변경하면 되기 때문에 수행 속도가 O(1)이 됩니다.
하지만 삽입 또는 삭제하려는 노드에 접근하기까지의 시간도 고려해야 합니다.
따라서 최악의 경우 시간복잡도가 O(n)이 될 수도 있습니다.
- 동적인 크기 조정 :
연결 리스트는 메모리에 연속적으로 저장되지 않기 때문에 크기를 유연하게 조정할 수 있습니다.
이로 인해 메모리가 불필요하게 사용되지 않습니다.
- Linked List(연결 리스트)의 단점
- 접근의 어려움 :
원하는 노드에 도달하기 위해 헤드 포인터부터 각 노드를 거쳐서 접근해야 하기 때문에 O(n)의 시간이 소요됩니다.
- 메모리 오버헤드가 발생하기 쉬움 :
단일 연결 리스트는 시작을 가리키는 헤드 포인터, 각 노드의 포인터 등 실제로는 유용하지 않은 데이터를 저장해야 하는 메모리 오버헤드가 발생합니다.
- 높은 캐시 미스 확률 :
캐시 메모리는 참조 지역성(Locality of Reference)의 원리를 활용하여 작동합니다.
이는 한 번 참조된 데이터에 인접한 메모리에 있는 데이터도 참조될 가능성이 높다는 원리입니다.
연결 리스트는 메모리에 연속적으로 저장되지 않기 때문에 각 노드 주변에 이전, 다음 노드가 위치하지 않을 가능성이 높습니다.
따라서 캐시 미스 확률이 높다고 할 수 있습니다.
그렇다고 해서 캐시 미스가 반드시 일어난다고 할 수 없습니다.
우연히 다음 노드가 이전 노드 주변에 저장될 수도 있습니다.
참 고 자 료
- [자료구조] 연결리스트란 (Linked List) | Kkang
