연결 리스트
연결 리스트는 요소들이 서로 붙어서 저장되는 배열(Array)와 다르게, 요소들이 서로 떨어져서 존재하며 다음 요소를 가리키는 '포인터'를 통해 요소들이 서로 연결되어 저장되는 자료구조이다. 그리고 연결 리스트에서는 각 요소를 노드(Node)라는 용어로 부른다.
아래 그림에서 HEAD는 리스트의 가장 앞 노드를 가리키는 포인터이며, TAIL은 리스트의 가장 뒷 노드를 가리키는 포인터이다. 각 노드는 내부적으로 리스트의 다음 노드를 가리키는 next 포인터를 가지고 있어, 노드들이 서로 연결되고 리스트 전체를 순회할 수 있게 된다.
단일 연결 리스트의 구조 -
출처
위 그림은 각 노드가 다음 노드를 가리키는 하나의 next 포인터를 가지는 '단일 연결 리스트'의 구조이며, 이와 달리 각 노드가 이전 노드를 가리키는 prev 포인터를 추가로 가지는 '이중 연결 리스트'도 존재한다.
자바스크립트만 공부하신 분이라면, 이러한 의문을 가질 수도 있다.
그냥 배열을 쓰면 되지 왜 이런 복잡한 자료구조를 쓰는거지? 연결리스트가 어디에 필요할까?
사실 자바스크립트만 공부하고 다른 프로그래밍 언어(C++, Java 등)들을 공부해 본 적이 없다면 연결 리스트의 필요성을 이해하기란 쉽지 않다. 이를 이해하기 위해서는 다른 객체지향 언어들이 배열을 어떻게 지원하는지 이해해야 한다.
자바스크립트에서는 단순히 배열을 만들고, push 명령어를 통해 인자를 배열에 넣어주면 된다. 우리가 넣어준 인자의 갯수가 곧 배열의 크기가 된다. 즉, 자바스크립트에서의 배열은 그 크기가 동적으로 변경되는 동적 자료구조이다.
하지만, 다른 많은 프로그래밍 언어들에서는 프로그래머가 배열을 선언할 때 그 배열의 크기를 미리 정해준 후 사용해야 한다. 만약 내가 처음에 people이라는 배열의 크기를 5로 설정했다면, 5개보다 많은 인자를 people 배열에 넣을 수 없다는 뜻이다. 5개보다 많은 인자를 people 배열에 넣으려면 빈 배열을 더 큰 크기로 다시 만든 기존 배열 인자들을 옮기거나, 다른 복잡한 방법들을 사용해야 한다.
이 때 유용하게 사용할 수 있는 자료구조가 바로 연결 리스트이다. 연결 리스트는 노드들이 각자 따로 존재하고 단순히 포인터로 연결되었을 뿐이므로, 크기 제한이 존재하지 않는다. 따라서, 배열을 사용할 때 배열의 크기가 빈번하게 변경되어야 한다면 연결 리스트를 배열 대신 사용하는 것이 좋은 선택일 수 있을 것이다.
자바스크립트에서는 push와 pop이 알아서 배열의 크기를 조절해주기 때문에 연결 리스트를 사용할 일은 거의 없다. 하지만, 이미 위치를 알고 있는 배열의 요소를 삭제하는 작업이 매우 빈번하게 일어나는 경우에는 유용하게 사용할 수 있을 것이다.
배열의 경우, 중간에 있는 요소를 삭제하기 위해서는 요소를 삭제한 후 삭제한 요소 이후의 모든 나머지 배열 요소들을 하나씩 앞으로 옮겨주는 작업이 필요하다. 하지만 연결 리스트의 경우 단순히 삭제하고자 하는 노드의 앞 노드 포인터 (이중 연결 리스트라면 뒷 노드 포인터도 포함)가 가리키는 노드만 변경해주면 삭제 작업이 완료된다.
배열에서 요소 삭제가 비효율적인 이유 -
출처
해시 테이블
해시 테이블이란 빠른 시간 내에 주어진 '키(key)'에 대응하는 '값(value)'을 찾기 위해 사용하는 자료구조로, 방대한 양의 데이터들에 대한 인덱싱을 빠르게 하기 위해 사용한다.
숫자 인덱스(index)만을 사용하여 각 요소들에 접근하는 배열과 다르게, 해시 테이블은 문자열 타입의 '키' 가 주어지면 이를 해시 함수(Hash Function)를 통해 숫자 인덱스로 변환한 후 이 인덱스를 기반으로 실제 데이터가 저장된 배열에 접근한다. 해시 테이블에서는 이 배열을 버킷(Bucket)이라고 부른다. 사실 버킷은 굳이 배열이 아니더라도 해시 함수의 결과 인덱스 값을 통해 인덱싱이 가능한 어떠한 자료구조로 구현되어도 좋다.
해시 테이블의 구조 -
출처
이 쯤에서 우리는 연결 리스트를 공부했을 때와 유사한 의문점을 가질 수 있다. 우리는 이미 자바스크립트에서 객체(Object)를 사용해 이미 (키, 값) 쌍을 저장할 수 있는데, 해시 테이블이 어디에 필요하지?
결론부터 말하면 자바스크립트에서는 필요없다. 해시 테이블을 사용해 암호화라도 구현할 것이 아니라면 말이다. 우리가 편하게 사용하고 있던 객체 문법은 사실 해시 테이블을 자바스크립트에서 보다 쉽게 사용할 수 있도록 제공된다고 생각하면 될 것 같다.
사실 자바스크립트의 객체는 내부적으로 해시 테이블보다 더 빠르게 동작하는 다른 구현을 사용했다고 하는데, 정확히는 모르겠다. 궁금한 사람은 아래 링크를 참고하자.
https://stackoverflow.com/questions/10256974/under-the-hood-are-javascript-objects-hash-tables
