Linked List?

리스트 자료구조 중 하나로 순서가 있는 데이터를 늘어놓은 자료구조이다.
리스트 자료구조에는 대표적으로 선형 List(배열)과 Linked List가 있다.

선형 리스트, 배열과의 차이

연산 종류	Array	Linked List
인덱스 접근	O(1)	O(N)
검색	O(N)	O(N)
삽입	O(N)	O(1)
삭제	O(N)	O(1)
메모리	고정 크기	동적 크기

인덱스 접근이 잦은 경우에는 배열을 사용하는 것이, 특정 인덱스의 삽입/삭제가 잦은 경우에는 Linked List를 사용하는 것이 좋다.

---

다시 돌아가서 Linked List를 알아보자!

Linked List는 배열처럼 물리적으로 연결되어있는 것이 아니라, 포인터를 활용해서 논리적으로 연결시키는 자료구조이다.

A에서 F까지 데이터가 순서대로 나열되고, 각 데이터가 화살표로 연결되어있다.
A는 B를 가리키고, B는 C를 가리키고, C는 D를 가리킨다. 현재 노드가 다음 노드를 가리키며 데이터가 순서대로 나열된다.

하지만, 주의해야할 점이 두 가지 있다.

1. 어느 노드를 건너뛸 수 없다.
2. 현재 노드에서 이전 노드를 알 수 없다.

이런 특징을 가진 자료구조를 연결 리스트, Linked List라고 한다.

Linked List를 구현하기 위해서는 두 가지 요소가 필요하다. 1️⃣ 저장할 데이터, 2️⃣ 다음 노드를 가리킬 포인터다.

앞서 A에서 F까지의 데이터가 나열된 Linked List는 엄밀히 보자면 아래와 같은 구조로 연결되어있는 것이다.(생략하여 A에서 C만 표현하였다)

용어 정리

• head node - 맨 앞의 노드
• tail node - 맨 끝의 노드
• predecessor node - 특정 노드의 앞쪽 노드
• successor node - 특정 노드의 뒤쪽 노드

C 언어 구현

Struct 정의

1. ListNode: int 데이터 타입의 item을 가지고, 다음에 연결된 노드 next를 가진 Node의 구조체

   typedef struct _listnode
   {
   	int item;
   	struct _listnode *next;
   } ListNode;

2. LinkedList: head 노드와 size 정보를 가진 Linked List 의 구조체

   typedef struct _linkedlist
   {
   	int size;
   	ListNode *head;
   } LinkedList;

검색 find 함수

Linked List는 선형 List의 A[i] 처럼 인덱스로 원소에 접근할 수 없다.

Linked List는 늘 head 노드에서 시작하여 순서대로 움직여야 한다.

찾고자 하는 index의 원소를 어떻게 찾을 수 있을까?

간단하다. index만큼 next 노드를 따라가보면 된다.

여기서 index = 2 의 값을 찾아보자.

head 노드에서 시작하여 2만큼 next 노드를 따라간다.

이렇게 index = 2의 노드를 찾을 수 있다.

구현

ListNode *findNode(LinkedList *ll, int index)
{

	ListNode *temp;

	if (ll == NULL || index < 0 || index >= ll->size)
		return NULL;

	temp = ll->head;

	if (temp == NULL || index < 0)
		return NULL;

	while (index > 0)
	{
		temp = temp->next;
		if (temp == NULL)
			return NULL;
		index--;
	}

	return temp;
}

삽입 insert 함수

Linked List는 이전 노드를 알 수 없다. 그리고 특정 노드를 건너뛸 수 없다.

따라서 삽입을 위해서는 우선 삽입을 위치의 노드를 찾아야 한다.

삽입을 원하는 위치가 2, 삽입하는 값이 5라고 하자. head 노드부터 시작하여 Node의 next 포인터를 따라가다가 원하는 index에 도달한다.

삽입 전 prev 노드와 cur 노드 사이에 새로운 값을 추가해야한다. 아래 두 과정을 거쳐 삽입을 완료할 수 있다.

1. prev 노드의 next 포인터가 새로운 노드를 가리키게 한다.
2. 새로운 노드의 next 포인터가 cur 노드를 가리키게 한다.

구현

int insertNode(LinkedList *ll, int index, int value)
{

	ListNode *pre, *cur;

	if (ll == NULL || index < 0 || index > ll->size + 1)
		return -1;

	// If empty list or inserting first node, need to update head pointer
	if (ll->head == NULL || index == 0)
	{
		cur = ll->head;
		ll->head = malloc(sizeof(ListNode));
		ll->head->item = value;
		ll->head->next = cur;
		ll->size++;
		return 0;
	}

	// Find the nodes before and at the target position
	// Create a new node and reconnect the links
	if ((pre = findNode(ll, index - 1)) != NULL)
	{
		cur = pre->next;
		pre->next = malloc(sizeof(ListNode));
		pre->next->item = value;
		pre->next->next = cur;
		ll->size++;
		return 0;
	}

	return -1;
}

삭제 remove 함수

삭제도 마찬가지다. 원하는 index 노드와 그 직전 노드를 찾고 그 연결을 끊어주면 된다.

1. 삭제를 원하는 cur 노드를 찾는다.

2. prev 노드의 next 포인터를 next 노드로 바꿔준다. 잊지않고 cur 노드를 할당 해제(free)해준다.

구현

int removeNode(LinkedList *ll, int index)
{

	ListNode *pre, *cur;

	// Highest index we can remove is size-1
	if (ll == NULL || index < 0 || index >= ll->size)
		return -1;

	// If removing first node, need to update head pointer
	if (index == 0)
	{
		cur = ll->head->next;
		free(ll->head);
		ll->head = cur;
		ll->size--;

		return 0;
	}

	// Find the nodes before and after the target position
	// Free the target node and reconnect the links
	if ((pre = findNode(ll, index - 1)) != NULL)
	{

		if (pre->next == NULL)
			return -1;

		cur = pre->next;
		pre->next = cur->next;
		free(cur);
		ll->size--;
		return 0;
	}

	return -1;
}