배열과 링크드리스트
배열(Array)
배열은 정적 자료구조라고 불립니다. 그래서 배열을 만들기 위해서는 미리 크기를 정해놓게 되는데요. 그렇게 되면 해당 크기 만큼의 연속된 메모리 주소를 할당 받게 됩니다.
연속된 메모리 주소를 할당 받고 있기 때문에 데이터가 인덱스(index)라는 것을 갖게 됩니다. 우리가 array[0] 같은 식으로 배열에 접근할 때 대괄호([]) 안에 숫자가 index입니다(JavaScript 기준).
index를 갖게 된다는 것은 즉 임의 접근이 가능하다는 장점이 있는 거죠. 그러므로 접근과 탐색에 용이합니다.
하지만 크기를 미리 정해놓았기 때문에 수정하는 것이 불가능합니다. 또한 이미 크기를 정해 놓은 터라 해당 배열 크기 이상의 데이터를 저장할 수 없다는 단점이 있습니다.
연결 리스트(Linked List)
링크드 리스트, 또는 연결 리스트는 동적 자료구조라고 불립니다. 그러므로 크기를 정할 필요가 없습니다. 또한 배열처럼 연속된 메모리 주소를 할당 받지 않습니다.
대신 노드(Node)라는 게 존재하며, 그 노드 안에 데이터가 있고, 다음 데이터를 가리키는 주소를 가지고 있습니다. 그런 식으로 연결되어 이어진 형태인 거죠.
연결 리스트는 위에서 말한 것처럼 크기를 정해 놓지 않았기 때문에 크기의 제한이 없습니다. 그로 인해 데이터 추가, 삭제가 자유롭다는 장점이 있습니다.
반면에 배열처럼 연속적인 메모리 주소를 할당 받지 않았기 때문에 임의로 접근하는 것이 불가능합니다. 그 말은 즉슨 데이터를 탐색할 때 순차적으로 접근해야 한다는 것입니다. 단점이라고 한다면 단점일 수 있는 거죠.
차이점
위에서 언급한 것을 아래 간단하게 표로 정리하면 이렇습니다.
배열(Array) 연결 리스트(Linked List)
정적 자료구조 동적 자료구조
미리 크기를 정해 놓음 크기를 정할 필요가 없음
연속된 메모리 주소를 할당 받음 연속된 메모리 주소를 할당 받지 않음
접근, 탐색 용이 추가, 삭제 용이
index 존재 Node 존재
