각 노드가 데이터와 포인터를 가지고 일렬로 연결되어 있는 방식으로 데이터를 저장하는 자료구조
- 논리적 저장 순서와 물리적 저장 순서 일치하지 않음
- 데이터 접근:
O(n)
첫 번째 노드부터 순차적으로 요소에 액세스 해야 함(random access 불가) - 데이터 탐색:
O(n) - 데이터 삽입, 삭제:
O(1)
각각의 원소는 자기 자신 다음이 어떤 원소인지 기억하고 있기 때문에 이 부분만 다른 값으로 바꾸면 된다. 단, 탐색이O(n)이기 때문에 탐색이 필요한 경우O(n) - 포인터를 위한 추가 공간 필요
- 프로그램 작성이 어려움
