Linked List(연결 리스트)
Linked List란, 데이터를 논리적 순서에 따라 입력하지만, 물리적 주소는 순차적이지 않는 자료구조를 말한다.
Linked List의 특징:
장점: Linked List에 데이터를 삽입하거나, 삭제시에 각 데이터가 가지고 있는 링크만 변경하면 되므로, 다른 데이터의 영향없이 빠르게 가능하다.
단점: 배열의 인덱스 대신에 각 데이터가 이전 위치 및 다음 위치를 가리키는 링크를 가지고 있기 때문에, 데이터에 한번에 접근할 수는 없고, 연결되어 있는 링크를 따라가야 하기 때문에, 배열에 비해 속도가 느리다.
Array(배열)
Array란, 데이터를 논리적 순서에 따라 순차적으로 데이터를 입력하며, 물리적 주소 또한 순차적인 자료구조를 말한다.
Array의 특징:
장점: 인덱스를 가지고 있어서 원하는 데이터에 한번에 접근이 가능하기 때문에 접근속도가 빠르다.
단점: Array에 데이터를 삽입하거나 삭제할 시에 배열을 통째로 복사해서 삽입/삭제가 이루어지고, 삽입/삭제가 이루어진 위치의 다음부터 모든 데이터의 위치를 변경해야 하기 때문에, 삽입/삭제 때마다 데이터의 위치를 바꾸는 데만 많은 리소스를 사용하게 된다.
1. 접근 속도(Access)
Linked List: 최소 한번은 리스트를 순회해야 하기 때문에, 시간복잡도는 O(n)이다.
Array: 인덱스로 접근하기 때문에, 시간복잡도는 O(1)이다.
2. 삽입/삭제 속도(Add/Remove)
Linked List: 어느 곳에 삽입/삭제를 하던간에 리스트를 순회해야 하기 때문에, 시간복잡도는 O(n)이다.
Array:
- 데이터를 삽입/삭제시에 삽입 또는 삭제될 위치 그 이후의 데이터를 한 칸씩 미뤄야하는 추가과정과 시간 등 리소스가 소비됨.(Linked List는 필요없음)
- 또한, 데이터를 삽입시에 모든 공간이 다 꽉 차버렸다면, 새로운 메모리 공간이 필요함.(Linked List는 필요없음)
목적과 상황에 따라 선택해야 하는 자료구조
Linked List를 사용해야 하는 경우: 데이터의 삽입/삭제가 자주 일어나야 한다면 사용
Array를 사용해야 하는 경우: 데이터의 삽입/삭제가 많이 없고, 대신에 데이터의 접근이 자주 일어나야 한다면 사용