기타 자료 구조 : Linked-list (연결 리스트)

Kim Yuhyeon·2022년 4월 6일

cpp linked list 알고리즘 자료구조

알고리즘 + 자료구조

목록 보기

33/161

Linked-list (연결 리스트)

리스트?

'일정한 순서'의 나열 로,
어떤 정의에 의해서 결정된 '논리적인 순서'의 나열이다.

리스트의 순서는 데이터가 저장되는 물리적 위치와 상관없이 사람들의 머릿속에 인식되는 논리적인 순서, 혹은
리스트에 나타나는 원소들간의 의미적인 순서를 의미한다.

배열과 리스트의 차이 ?

배열

인덱스로 표현되는 '순서'가
배열 원소의 메모리 공간에서 물리적 의미를 의미함.

리스트

리스트의 '순서' 개념은
어떤 정의에 의해 결정된 '논리적인 순서'.

원소들의 물리적인 저장 순서나 위치와 무관하게
원소들 간의 논리적인 순서만 유지한다.

리스트의 구현 방법

1) 포인터를 이용한 방법

원소값을 저장하는 공간 과
다음 원소를 가리키는 위치 정보를 저장하는 공간 을
같이 구현하는 방법이다.

👍 장점

필요한 만큼 객체를 생성하기 때문에 낭비되는 부분이 없다.

👎 단점
포인터를 저장하는 공간이 필요하기 때문에 객체 1개당 필요한 메모리가 배열보다 커지는 점이 있다.

2) 배열을 이용한 방법

배열을 만들어놓고 중간에 데이터를 삽입한다.

👍 장점

속도가 빠르다.

👎 단점

삽입하려는 위치 뒤에 있는 데이터를 다 한 칸씩 뒤로 밀고 삽입해야 한다.
삭제할 때도 삭제하려는 위치 뒤에 있는 데이터를 한 칸씩 앞으로 땡겨야 한다.

이러한 동작들은 원소의 수에 비례해서 프로그램 수행 시간을 엄청나게 증가시킬 수 있다.

리스트를 일반적으로 포인터를 이용해서 구현한다.

구조

Node(노드)

링크드 리스트에 데이터가 저장되는 객체 1개

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

data : 구조체 내부에는 데이터를 저장
next : 다음 노드의 주소를 저장

ListNode* head = NULL;

head : 링크드 리스트의 처음을 가리킴
데이터에 접근하려면 head 변수를 통해서
접근할 수 있다.

연산

삽입

데이터는 리스트의 첫번째 또는 원하는 위치에 삽입할 수 있다.

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에서 인자 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);
	}
}

길이

링크드 리스트의 길이를 구하려면
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";
}