23. 06.20 자료구조 2. 연결 리스트(Linked List)

 연결 리스트란 이름 그대로 요소 간의 연결로 이루어진 자료구조이며 일반적으로 이런 요소들을 노드라고 한다. 각 노드는 데이터 값과 다음 노드의 주소를 가진다. 그래서 이걸 왜 쓰냐하면 정해진 공간을 다 차지하는게 아니라서 메모리를 적게 먹는다. 그리고 각각의 데이터가 분리 되어 있어서 데이터를 추가하거나 삭제 시에 편하다 데이터에 주소값만 추가해서 노드로 사용하면 되기에 다른 데이터에 영향을 주지 않는다. 주소만 바꾸면 된다 그래서 유동적으로 사용하기에 좋다. 하지만 장점만 있으면 다른 구조들이 왜 있겠어 각 데이터가 연결되어 있어서 필요한 것을 찾으려면 쭉 타고 가야하는 단점이 있다. 그래서 당연히 느리다 그리고 크게 세가지 형태가 있는데 단일형과 이중, 원형이 있다. 단일형은 기본형 다음 주소값만 가진 것이고, 이중형은 전에 주소값도 가진 형태, 원형은 끝에서 처음으로 연결하는 게 추가된 형태이다.

 나는 이 노드를 이미 본 적이 있었다. 모두 그런 건 아니지만 종종 게임마다 원하는 스킬을 위해 아래에 스킬을 하나찍 타고 올라가야하는 경우가 있는데 이 과정에서 바로 중요한 스킬을 향해 나갈 수도 있고 중간에 사이드에 있는 다른 스킬들을 선택해서 갈 수도 있다. 혹은 중요한 스킬 하나보다 여러 스킬을 고르는 경우도 있다. 그렇게 연결이 되어야만 내가 원하는 스킬을 사용할 수 있다. 그리고 이렇게 스킬 뿐 아니라 연결해서 사용하는 게임 시스템의 경우에 유저들끼리 노드라는 명칭을 많이 사용한다. 그래서 단일형 노드는 과거 스킬 초기화 라는게 없던 시절의 게임 같고 원형은 전체 초기화만 있던, 그리고 이중형은 하나씩 취소할 수 있는 시스템과 비슷해 이렇게 기억하면 오래 기억할 것 같다. 

 연결 리스트는 배열과 많이 비교되는데 가장 큰 차이는 인덱스와 메모리라고 생각한다. 배열에서의 인덱스는 배열에 접근하기 위한 식별자로 큰 의미를 가지는데 리스트에서는 그저 순서를 나타내는 것일 뿐 어떤 데이터를 확인 하려면 하나씩 타고 가야한다. 그리고 메모리 구조에서 배열은 연속된 구조를 가져 연병장에서 아침 정모 하듯이 규칙에 맞춰서 있지만 리스트는 당나라 군대마냥 정해진 공간 안에 흩어져 있어 다음 주소를 알아야만 찾을 수 있다. 

 그리고 배열 리스트란 것도 있어서 머리 아프게 하는데 배열로 리스트를 구현할 것으로 기존 배열에 길이가 정해지면 바꿀 수 없다는 점(정적 메모리)을 보완해 동적 메모리를 사용하는 점이 다르고 대부분의 기능은 비슷하다.  물론 이것도 장점만 있진 않고 동적 메모리를 사용하는만큼 기존 정적 메모리에 비해 메모리 낭비가 생길 수 있다. 자유와 책임 같은 거다. 자바스크립트는 이 배열 리스트를 지원한다.

 

조사하다보니 시간 복잡도 O(1)이나 O(n) 등의 내용이 나오는데 이건 나중에 하고 일단 자료구조부터 알자