linked list는 노드로 구성이 되어 있으며
각 노드가 데이터와 포인터를 가지고 한 줄로 연결된 방식의 자료구조이다.
여기서 포인터는 각 노드를 연결하는 역할을 한다.
linked list는 단일 연결 리스트와 이중 연결 리스트 등이 있다.
linked list에는 head와 tail이 있는데
head에서 시작하여 포인터를 따라가면 tail에 도착하는 구조이다.
이중 연결 리스트는 위의 예시에서 봤을 때 포인터를 단방향에서 양방향으로 이어주면 된다.
(이중 연결 리스트에서는 tail에서 시작하여 포인터를 따라갈 수 있다.)
시간 복잡도
linked list는 배열과 다르게 index가 없다.
그래서 값을 가져오기 위해서는 포인터를 따라
일일이 다 검색을 해줘야 하기에 시간 복잡도는 O(n)이 된다.
추가하기 삭제하기도 마찬가지로 그 값을 찾아 추가하고 삭제하기에 O(n)이 된다.
만약 access과정이 필요 없다면 포인터를 자르고 연결하는 과정만 필요하기에 O(1)이 된다.
댓글