자바스크립트에서 배열은 사기적인 자료구조입니다. C 와 같은 옛날 언어들의 배열은 직접 메모리를 관리해줘야 했으므로 정말 불편하였지만, 자바스크립트 배열은 직접 메모리를 관리할 필요 없이 사용 가능토록 다양한 기능들이 추가된 현대적인 형태의 배열입니다.
자바스크립트 배열을 생각하면서 자료구조를 공부한다면, 자료구조 학습에 방해가 될 수 있습니다. 만일 배열이 없었다면 어떻게 할까? 라는 출발점 부터 시작해 보는 겁니다.
연결리스트는 노드와 노드 간에 참조 관계가 형성되어 있는 리스트 입니다. 예를 들어, A, B, C 라는 세 개의 노드가 있으면 메모리 공간 상에 각자의 독립적인 공간을 할당받아 배치되어 있기 때문에 컴퓨터의 입장에서는 A 다음에 B 가 있음을 알 수가 없습니다. 따라서 A 다음에 B 가 있음을 알 수 있도록 서로 이어주므로 연결 리스트 혹은 링크드 리스트라고 부릅니다.
연결리스트는 구현하는 방식 혹은 목적에 따라 종류는 다양해질 수 있습니다. 아래는 그 중 일부 입니다.
참조 관계가 A→ B → C 와 같이 하나의 방향으로 형성되어 있는 리스트를 의미합니다.
참조 관계가 A→←B→←C 와 같이 서로가 서로의 참조하는 리스트를 의미합니다.
조회, 수정, 삭제, 삽입 모두 O(n) 입니다. 최악의 경우 처음 부터 끝 까지 순회 후 마지막 참조에 해당하는 노드를 조회, 수정, 삭제, 하거나 마지막 노드의 끝에 새로운 삽입하므로 O(n) 이 걸립니다.