1. Linked List

리스트는 크게 두가지로 구현할 수 있다.
1. 배열
2. Node, Pointer

1. 배열

배열로 구현했을 때의 장점 및 단점 시간복잡도를 계산해보자.

삽입

기존에 있던 원소들을 뒤로 이동시켜야 하기 때문에 최악의 경우 O(N) 시간복잡도를 갖게된다.
그러나 마지막 원소에 넣게 된다면 현재 원소의 길이를 유지하고 있기 때문에 O(1)의 시간복잡도로 삽입 할 수 있게 된다.

삭제

이 역시 기존에 있던 원소들을 한칸씩 당겨야 하기 때문에 최악의 경우 O(N)의 시간복잡도를 갖게된다.
그러나 마지막 원소를 삭제하게 된다면 현재 원소의 길이를 유지(마지막 인덱스를 알 수 있음)하고 있기 때문에 O(1)의 시간복잡도로 삭제할 수 있게 된다.

검색

원소를 하나씩 검사하며 완전 탐색을 해야하기 때문에 최악의 경우 O(N)의 시간복잡도를 갖게 된다.

특정 인덱스 접근

배열로 구현하고 있기 때문에 O(1)의 시간복잡도를 갖게 된다.

단점

배열의 크기를 미리 정의를 해놓아야 하며 사용하지 않는 배열에 대해 메모리 낭비가 발생할 수 있다. 또한 배열이 꽉 찼을 때 더블링이 발생하며 O(N)의 시간복잡도로 데이터를 옮겨야 하는 상황이 발생할 수 있다.

2. Node, Pointer (단방향 연결 리스트)

위와 같은 단점을 극복하기 위해 Node, Pointer를 통한 연결리스트가 등장하였다.

삽입

원하는 인덱스로 가서 연결을 끊고 새로운 노드를 연결시켜주면 된다. 따라서 시간 복잡도는 탐색 비용인 O(N)의 시간 복잡도를 갖는다.

삭제

이 역시 삽입과 같은 이유로 O(N)의 시간복잡도를 갖는다.

검색

Node 하나씩 탐색하며 원하는 데이터를 비교해야 하기 때문에 O(N)의 시간복잡도가 걸린다.

특정 인덱스 접근

Node를 타고 가며 인덱스를 세야 하기 때문에 O(N)의 시간복잡도가 걸린다.

그럼 왜 사용?

삽입, 삭제, 검색, 특정 인덱스 접근 모두 O(N)의 시간복잡도를 갖는다. 그러나 필요한 만큼만 메모리를 사용할 수 있으므로 메모리 효율 측면에서 값어치 있는 자료구조이다..!

자세한 내용은 여기서 확인 바란다.