Linked List

in CS on Data Structure


Array에서는 검색, 갱신의 시간복잡도가 O(1)이었지만, 삽입 삭제의 시간복잡도가 O(n)으로 많은 시간이 걸렸다. 이를 해결하기 위한 자료구조가 linked list이다.

1. 장점 및 특징

Linked list에서 각각의 원소들은 자기 자신과 다음에 어떤 원소가 오는지 만을 기억하고 있다. 따라서 이 다음에 오는 원소 부분을 다른 값으로 바꿔주면 삭제와 삽입을 O(1)만에 해결할 수 있는 것이다.

2. 단점

하지만 연결 리스트에서도 원하는 위치에 삽입을 하려고 하면 원하는 위치를 찾는 과정에서 첫 번째 원소부터 차례대로 확인해봐야 한다는 것이다. Linked list는 array와 달리 논리적 저장 순서와 물리적 저장 순서가 일치하지 않기 때문이다. 따라서 어떤 원소를 삭제, 혹은 추가하려고 할 때 그 원소를 찾기 위해서 O(n)의 시간이 추가적으로 발생한다.

이런 단점을 갖고 있다 하더라도, linked list는 많은 자료구조의 근간이 된다. Tree가 바로 그 대표적인 예이다.

3. 종류

연결 리스트에는 여러 종류가 있다.

  1. 단일 연결 리스트
  2. 이중 연결 리스트
  3. 환형 연결 리스트 (마지막 노드와 처음의 노드를 연결 시켜 원형 구조를 만든 것이다)

4. 시간 복잡도

  1. 탐색 : O(N)
  2. 삽입 : O(1)
  3. 삭제 : O(1)

그런데 흔히 linkedlist의 삽입/삭제의 시간복잡도는 O(1)이라고 알려져 있고, 여기 에서도 나와 있듯이 LinkdList에서의 시간 복잡도는 O(1)이라고 나와있다.

  • 삽입/삭제를 할 때 위치를 찾기 위해 처음붜 탐색 : 탐색 + 수정(삽입 삭제)
  • O(1) : 오로지 수정 작업만 봤을 때

라고 이해하면 편하다.

5. array 와의 비교

메모리 할당

array에서는 메모리는 array가 선언되지마자 compile time에 할당된다. 이걸 정적 메모리 할당이라고 한다. array 같은 경우는 stack 영역에 메모리 할당이 이루어진다.

LinkedList에서 메모리는 새로운 node가 추가될 때 runtime에 할당된다. 이것을 동적 메모리 할당이라고 한다. LinkedList는 heap 영역에 메모리 할당이 이루어진다.

결론적으로, 삽입 삭제가 빈번하면 LinkedList,

데이터의 접근이 중요하면 array를 사용하는 것이 좋다.

6. ArrayList?

  1. 내부적으로 데이터를 배열에서 관리하여 데이터의 추가, 삭제를 위해 임시 배열을 생성해 데이터를 복사한다.
  2. 대량의 자료를 추가/삭제 하는 경우 데이터의 복사가 많이 일어나 성능 저하가 발생한다.
  3. 중간에 데이터를 삽입하기 위해서는 연속된 빈 공간이 있어야 한다.
  4. 인덱스를 가지고 있어서 한 번에 참조가 가능해 데이터 검색에 유리하다.

ArrayList는 삽입 삭제를 할 일이 없거나 배열의 끝에서만 할 경우 유용하다. 원소에 빠르게 접근할 뿐만 아니라 원소들이 메모리에 연속적으로 위치해 있기 때문에 CPU 캐시 효율도 높다.

7. C++

c++에서 linked list를 만들어 보겠다.

우선 Node 구조체를 선언해준다.

typedef struct NODE {
  int data;
  struct NODE* next;
} node;

데이터를 저장할 data, 다음 노드를 가리킬(주소를 저장할) 자기참조 구조체 포인터 변수를 가지고 있다. 이 자기참조 구조체 포인터 변수는 자기 자신의 타입을 참조하는 포인터변수다.

그리고 첫번째 머리노드, head를 만들어보자.

int main() {
  node* head = (node*) malloc(sizeof(node));
}

malloc 함수로 node의 크기만큼 동적할당을 했다. 반환되는 주소값을 (node*) 자기 참조 구조체 포인터형으로 형변환을 해준다.