[C++] 연결 리스트(Linked List)

[C++] 연결 리스트(Linked List)

반응형

연결 리스트

물리적으로 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법을 연결 리스트(Linked List)라고 한다.

연결 리스트는 배열의 단점을 보완하고자 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조

연결 리스트 기본 구조와 용어 노드(Node): 데이터 저장 단위(데이터 값, 포인터)로 구성 포인터(Pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간

3가지 종류의 연결 리스트가 있다 단순 연결 리스트 원형 연결 리스트 이중 연결 리스트

단순 연결 리스트 구현

구조

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

​ 구조체 내부에 데이터를 저장하는 data와 다음 노드의 주소를 가리키는(저장하는) next 변수가 있다.

ListNode* head = NULL;

​ 또한 연결 리스트의 처음을 가리키는 head(헤드 포인터)라는 변수가 있다. 데이터에 접근하려면 이 변수를 통 해서 접할 수 있다.

데이터 삽입 데이터는 리스트의 처음 또는 원하는 위치에 삽입할 수 있다. head에 데이터가 없다면 가장 처음에 데이터가 삽입되고, 데이터가 있다면 인자로 전달된 position의 위치에 노드가 삽입된다. 데이터의 길이보다 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" << "

"; 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); } }

데이터 출력

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

"; }

모든 리스트를 탐색하면서 데이터를 출력하며 head부터 NULL까지 탐색해야한다.

출처: 1, 2

반응형

from http://good-potato.tistory.com/35 by ccl(A) rewrite - 2021-08-20 23:26:31