단일 연결 리스트(Singly Linked List) 설명과 예제 코드(C++)

algorithm

링크드 리스트(Linked List, 연결 리스트)는 데이터의 집합을 저장하기 위해 사용되는 데이터 구조입니다. 연속적인 자료구조로 되어있고 배열과 비교하여 장단점이 있습니다.

링크드 리스트는 다음의 속성을 갖고 있습니다.

  • 연속되는 항목들이 포인터로 연결됨
  • 마지막 항목은 NULL을 가리킴
  • 동적으로 리스트의 크기가 커지거나 줄어들 수 있음
  • 필요한 만큼 사용하기 때문에 불필요한 메모리를 낭비하지 않음

링크드리스트는 배열로 구현할 수 있고, 포인터를 이용하여 구현할 수도 있습니다. 배열의 경우 속도가 빠르지만 일정한 메모리를 미리 확보해야 하는 단점이 있습니다. 반면에 포인터를 이용하는 경우 필요한 만큼 객체를 생성하기 때문에 낭비되는 부분이 없습니다. 하지만 포인터를 저장하는 공간이 필요하기 때문에 객체 1개당 필요한 메모리가 배열보다 커지는 점이 있씁니다.

이 글에서는 샘플 코드로 포인터를 이용한 단일 연결 리스트(Singly Linked List)를 C++로 구현하였습니다. 완성된 코드는 GitHub - Singly Linked List에 있습니다 코드만 참고하시는 분들은 GitHub를 확인해주세요.

링크드 리스트 데이터 구조

링크드 리스트에 데이터가 저장되는 객체 1개를 노드(Node)라고 합니다.

코드로 이렇게 정의할 수 있습니다. 구조체 내부에는 데이터를 저장하는 data와 다음 노드의 주소를 저장하는 next변수가 있습니다.

typedef struct ListNode {
	int data;
	struct ListNode* next;
} ListNode;

그리고 링크드 리스트의 처음을 가리키는 head라는 변수가 있습니다. 데이터에 접근하려면 이 변수를 통해서 접근할 수 있습니다.

ListNode* head = NULL;

링크드 리스트에 데이터 삽입

데이터는 리스트의 첫번째 또는 원하는 위치에 삽입할 수 있습니다. 아래 코드는 리스트의 삽입 코드입니다. head에 아무 데이터가 없다면 가장 처음에 데이터가 삽입되고, 데이터가 있다면 인자로 전달된 position의 위치에 노드가 삽입됩니다. position의 값이 1이라면 가장 첫번째에 삽입됩니다. 데이터의 길이보다 position이 더 크다면 리스트의 가장 마지막에 노드가 삽입됩니다.

void InsertInLinkedList(ListNode**head, int data, int position) {
	ListNode* inserted = new ListNode;
	inserted->data = data;

	if (position == 1 || *head == NULL) {
		inserted->next = *head;
		*head = inserted;
	}
	else {
		ListNode* inserted_prev = *head;
		for (int i = 1; (inserted_prev->next != NULL) && (i < position-1); i++) {
			inserted_prev = inserted_prev->next;
		}

		ListNode* inserted_next = inserted_prev->next;
		inserted_prev->next = inserted;
		inserted->next = inserted_next;
	}
}

링크드 리스트의 길이

링크드 리스트의 길이를 구하려면 head부터 마지막 NULL까지 탐색해야 합니다. 아래와 같이 구현할 수 있습니다.

int ListLength(struct ListNode* head) {
	int len = 0;
	struct ListNode* current = head;
	while (current!= NULL)
	{
		len++;
		current = current->next;
	}
	return len;
}

링크드 리스트의 모든 데이터 출력

리스트의 길이를 구하는 코드와 같이 모든 리스트를 탐색하면서 데이터를 출력하면 됩니다.

void PrintList(struct ListNode* head) {
	struct ListNode* current = head;
	while (current != NULL)
	{
		cout << current->data << " -> ";
		current = current->next;
	}
	cout << "NULL\n";
}

링크드 리스트의 노드 삭제

위의 노드 삽입 코드와 같이, head에서 인자 position의 위치에 해당하는 노드를 삭제합니다. 삭제하려는 position에 노드가 없으면 가장 마지막 노드를 삭제합니다.

void DeleteNodeFromLinkedList(ListNode** head, int position) {
	if (*head == NULL) {
		cout << "List empty" << "\n";
		return;
	}
	ListNode* removed_prev;
	ListNode* removed;
	if (position == 1) {
		removed = *head;
		*head = (*head)->next;
		delete(removed);
	}
	else {
		ListNode* removed_prev = *head;
		removed = removed_prev->next;
		for (int i = 1; (removed->next != NULL) && (i < position-1); i++) {
			removed_prev = removed_prev->next;
			removed = removed_prev->next;
		}
		removed_prev->next = removed->next;
		delete(removed);
	}
}

완성된 코드

완성된 코드는 GitHub - Singly Linked List에 있습니다.

main을 실행해보면 노드가 생성되고 삭제되는 것을 볼 수 있습니다.

ListNode* head = NULL;
int main()
{
	InsertInLinkedList(&head, 4, 1);
	InsertInLinkedList(&head, 17, 1);
	InsertInLinkedList(&head, 1, 1);
	InsertInLinkedList(&head, 5, 1);

	PrintList(head);
	InsertInLinkedList(&head, 10, 1);
	PrintList(head);
	InsertInLinkedList(&head, 11, 3);
	PrintList(head);
	InsertInLinkedList(&head, 11, 9);
	PrintList(head);
	DeleteNodeFromLinkedList(&head, 1);
	PrintList(head);
	DeleteNodeFromLinkedList(&head, 3);
	PrintList(head);
	DeleteNodeFromLinkedList(&head, 10);
	PrintList(head);
}

실행 결과

5 -> 1 -> 17 -> 4 -> NULL
10 -> 5 -> 1 -> 17 -> 4 -> NULL
10 -> 5 -> 11 -> 1 -> 17 -> 4 -> NULL
10 -> 5 -> 11 -> 1 -> 17 -> 4 -> 11 -> NULL
5 -> 11 -> 1 -> 17 -> 4 -> 11 -> NULL
5 -> 11 -> 17 -> 4 -> 11 -> NULL
5 -> 11 -> 17 -> 4 -> NULL

참고

다음 글은 양방향 연결 리스트(링크드 리스트) 설명과 예제 코드(C++)입니다.

Loading script...
codechachaCopyright ©2019 codechacha