[JS] 연결 리스트

연결 리스트는 각 요소를 포인터로 연결하여 관리하는 선형 자료구조. 각 요소는 노드라고 부르며 데이터 영역과 포인터 영역으로 구성됨.

연결 리스트의 특징

• 메모리가 허용하는한 요소를 동적으로 제한없이 추가할 수 있다.
• 탐색 시간은 O(n)이 소요된다. → 순차 접근 방식을 사용하기 때문에 어떤 한 데이터를 찾기위해서는 순차적으로 노드를 타고 가야함.
• 데이터 추가와 삭제에서 데이터를 추가하는 행위 자체의 시간복잡도는 주소값만 바꾸면 되기에 O(1)이지만 추가하려는 데이터의 위치가 맨 처음이 아니고 그 이후라면 순차적으로 탐색하면서 해당 위치까지 가야하기 때문에 O(n)이 된다.

배열과 차이점

• 배열은 순차적인 데이터가 들어가서 메모리영역을 연속적으로 사용하는 반면 연결리스트는 데이터가 순차적이지 않기에 각 데이터가 퍼져있음. 연결리스트는 퍼져있는 메모리영역을 알기 위해 포인터를 사용하여 각 영역을 참조함.

이중 연결 리스트

• 양방향으로 이어지는 연결 리스트
• 단일 연결 리스트보다 자료구조의 크기가 조금 더 크다. → 포인터 변수가 하나 더 추가되어서
• 다음과 이전을 가리키는 포인터 두개가 있다.