자료구조
#.3 Linked List
Haksae
2022. 3. 9. 04:12
Linked List
1) Linked List (연결 리스트)
- 배열이 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조라면, 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조이다.
- 링크드 리스트 기본 구조와 용어
- 노드(Node): 데이터 저장 단위(데이터 값, 포인터)로 구성
- 포인터(pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간
- 배열은 데이터만 가지고 있는 반면, 링크드 리스트는 데이터 + 다음 데이터의 주소 값을 가진다.
- 배열은 미리 셋팅하고 데이터를 넣으므로, 데이터를 추가할 수 없다 혹은 어렵다. (원래는)
- 링크드 리스트는 포인터가 있기 때문에 추가하기 쉽다.
- 장점
- 데이터 추가나 삭제가 쉽게 가능하고, 빠르다. (시간 복잡도 O(1)) (그러나 노드까지 접근 시간이.. O(N)이기에 잘못하면 O(N)이다. 어쩌면 장점이 아니다..)
- 미리 데이터 공간을 할당하지 않고, 쓰는 만큼만 차지하기에 유연한 공간 활용이 가능하다.
- 단점
- 데이터 접근에 대한 시간이 늘어난다.
- 랜덤 엑세스가 안되기 때문에 검색이나 삽입과 같은 작업 시 노드를 찾아가는 과정이 비효율적이다.
- 시간 복잡도는 O(N)이다.
- 연결을 위한 별도의 데이터 공간이 필요하므로, 저장 공간 효율이 높지 않다.
- 중간 데이터 삽입 또는 삭제시, 앞 뒤 데이터 연결을 재구성해야하는 부가적인 작업이 필요하다.
- 데이터가 흩어져있다.
- 캐시히트 가능성이 굉장히 떨어진다. (캐시미스 발생)
- 페이지폴트까지 날 수도 있다.
- 데이터 접근에 대한 시간이 늘어난다.
2) Double Linked List (이중 연결 리스트)
- Linked List가 다음 노드의 주소값만 가졌다면, Double Linked List는 각 노드가 선행 노드와 후속 노드에 대한 주소값을 가지는 리스트이다.
- 위의 그림처럼 노드의 왼쪽 링크와 오른쪽 링크가, 각각 다른 노드의 링크들과 연결되어있고, 헤드도 노드로 이루어져 있다.
- 기존의 연결 리스트는 노드 중간에 삽입과 삭제가 어려웠다.
- 그러나 이중 연결 리스트는 리스트 전체를 방문하지 않아도 원하는 위치에 노드를 쉽게 추가하거나 삭제할 수 있다
참고자료