[자료구조] Linked List (연결 리스트)

개요

연결 리스트, 링크드 리스트라고 부름. 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 노드의 포인터가 다음이나 이전의 노드와 연결을 담당하게 된다.

종류로는 단일 연결 리스트, 이중 연결 리스트 등이 있다.

 

장점

자료의 추가와 삭제가 O(1)의 시간에 가능하다.

 

단점

특정 위치의 데이터를 검색해 내는데 O(n)의 시간이 걸린다.

 

사용하는 곳

연결 리스트를 발전시켜 사용하는 곳은 많은데, 라이브러리에서 사용하거나 (특히 JS) 스택이나 큐처럼 사용하는 곳이 명확하게 나와있지가 않다. 찾기가 힘들다.

참고자료

https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8

연결 리스트 - 위키백과, 우리 모두의 백과사전