1. Linked List vs Array

1) Linked List

Linked List(연결된 리스트)는 데이터가 임의의 메모리 공간에 저장되며, 리스트 요소의 순서에 따라 노드의 포인터 부분을 이용하여 데이터를 서로 연결시키는 리스트 자료구조이다. (연속적으로 저장되지 않는다.)

이 자료구조에서 각 데이터 요소는 노드(node)로 표현된다. 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성되며, 각 언어의 구조체로 구현한다. 어떤 노드가 다음 노드를 가리키는 포인터가 없는 경우(NULL), 그 노드는 Linked List의 마지막 노드(tail)임을 의미한다.

Linked List를 사용하면 노드의 삽입과 삭제 작업이 용이해진다. List의 크기에 구애받지 않고 현재 메모리 사용 상태에 따라 빈 공간에 동적으로 데이터를 저장할 수 있고, 삭제 또한 노드에 연결된 포인터를 다른 노드로 수정해주기만 하면 되기 때문에 효율적으로 구성할 수 있다.

단, 연결을 위한 링크(포인터)가 필요하기 때문에 메모리 이용 효율이 좋지 않으며, 링크를 찾는 시간이 필요하기 때문에 접근 속도가 느리다. 그리고 링크에 의해 리스트 요소의 순서가 구성되기 때문에 리스트의 중간 부분 노드의 연결이 끊어지면 그 다음 노드를 찾기 힘들어진다.

Linked List의 종류로는 4가지가 있다.

1. Singly Linked List
   단일 연결 리스트로, 다음 노드를 가리키는 포인터를 포함한다. tail이 NULL을 가리켜 노드의 끝을 표현한다. 선행 노드에 접근하기 어렵다.
   
2. Doubly Linked List
   양방향 연결 리스트로, 노드를 연결하는 link가 앞(prev)과 뒤(next)로 존재하여 선행 노드와 후속 노드에 접근할 수 있다.
   
3. Circular Linked List
   원형 연결리스트로, tail이 NULL을 가리키지 않고 첫 번째 노드를 가리켜 순환하도록 한다.
   
4. Circular Doubly Linked List
   원형 이중 연결리스트로, Doubly Linked List의 구조에서 첫 번째 노드와 마지막 노드가 서로 연결되어 있다. 시작 위치를 알기 위해 첫 번째 노드에 선행 노드로 NULL 값을 가진 head 노드를 추가한다.
   

• Head Pointer Node
  데이터를 가지지 않고, 첫 번째 또는 마지막 노드의 주소만 가리키고 있는 노드이다. 헤드 포인터를 추가함으로써 첫 번째 노드와 마지막 노드의 왼쪽 링크필드, 오른쪽 링크필드를 NULL 값이 아닌 노드의 주소를 대입함으로써 원형의 구조를 가져 삽입과 삭제를 용이하게 할 수 있다.

2) Array

또 다른 리스트 자료구조인 Array(배열)은 연속된 메모리 공간에 할당된 리스트이다.
예를 들어, int 타입의 Array의 arr[0](Array의 시작점)가 저장된 메모리 공간의 주소가 0x100이라면, 그 이후의 배열 요소는 0x104, 0x108, 0x112,...와 같은 연속된 공간에 저장된다. 따라서 배열의 요소에 접근할 때에 Array의 처음 주소만 알고 있다면 index를 통해 바로 접근할 수 있다는 장점이 있다.
Array에서 n번째 요소(Arr[n])에 접근할 때 발생하는 시간 복잡도는 O(1)이다.

하지만 Array는 데이터가 빈번하게 추가 또는 삭제되는 경우에 사용하기에는 효율적이지 않다. 배열에 요소를 추가 또는 삭제할 때 배열의 모든 요소를 최대 N개만큼 이동해야 하고, 그만큼 시간 복잡도가 증가한다.(단, 배열의 마지막에 요소를 추가하는 경우는 O(1)이다.)

또, 컴파일 시점에 배열의 크기만큼 메모리 공간을 정적 할당하기 때문에 메모리 공간의 낭비가 발생하거나 부족해질 수 있는데, 이 경우 배열을 재할당하고 기존 요소들을 복사해야 하므로 시간 복잡도는 O(n)이다.

Array와 Linked List의 특징을 비교하자면 다음과 같다.

1. Array는 연속된 메모리 공간에 존재하고, Linked List는 메모리 상에 분산되어 저장되어 있는 데이터들이 앞의 데이터와 뒤의 데이터를 기억하고 있는 형태로 존재한다.
2. Array에 저장되어 있는 데이터를 조회할 때에는 O(1)이 소요되지만, Linked List는 리스트의 시작점인 head부터 출발하므로 O(n)이 소요된다.
3. Array와 Linked List 모두 데이터를 추가할 때에는 O(1)이 소요된다.
4. Array는 요소를 삭제할 때 순서를 재설정하려고 요소를 옮기는 과정에 의해 O(n)이 소요되지만, Linked List는 link만 바꿔주면 되므로 O(1)이 소요된다.
5. Array는 컴파일 과정에서 메모리가 할당되는 정적 메모리 할당인 반면, Linked List는 런타임 환경에서 메모리가 할당되는 동적 메모리 할당이다.
6. Array는 Stack에 메모리가 할당되고, Linked List는 Heap에 할당된다.

이러한 개념을 통해 Linked List를 구현해보자.

2. Linked List 구현

1) Node 구조체 정의

먼저 각 노드의 구조를 정의한다. 일반적으로 각 노드는 데이터와 후속 노드를 가리키는 포인터로 구성된다.

typedef struct Node {
  int data;
  struct Node* link;
} Node;

2) Head Node 정의

헤드 포인터는 노드 구조체 인스턴스를 가리키는 포인터이며, Linked List의 시작점을 가리킨다. 이 헤드 포인터를 통해 Linked List의 모든 노드에 접근할 수 있다.
구조체 인스턴스에 대한 동적 할당 또는 포인터를 통한 접근에 사용한다.
단, 초기의 헤드 포인터는 가리키는 값이 아직 없기 때문에 NULL 값으로 초기화 한다.

Node* head = NULL;

3) 맨 앞에 Node 삽입

새로운 노드를 맨 앞에 추가할 때에는 새로운 노드를 동적으로 생성하고, Linked List의 헤드 포인터를 새로운 노드로 갱신해야 한다. 파라미터로는 현재의 헤드 노드와 추가할 데이터를 받는다.

Node* insertFirst(Node* head, int data) {
  Node* newNode = (Node *)malloc(sizeof(Node)); // 새로운 노드 생성
  newNode->data = data; // 데이터 할당
  newNode->link = head; // 새로운 노드의 링크를 현재 리스트의 첫 번째 노드를 가리키도록 설정
  return newNode;
}

4) 맨 뒤에 Node 삽입