[자료구조] 연결리스트(Linked List)

리스트

동일 특성을 갖는 항목들의 모임

 

선형리스트

순서에 따른 항목들의 모임

 

리스트의 구현

1) 배열

구현이 단순하나 삽입/삭제 연산이 비효율적이다.

정적인 구조로 크기가 고정되어 있다.

 

2) 연결리스트

구현이 복잡하나 삽입/삭제 연산이 효율적이다.

동적인 구조로 크기에 제한을 받지 않는다.

 

연결리스트의 구조

- 노드 구조 : 데이터 + 다음 데이터를 가르키는 주소(포인터) 필드로 구성

  다음 데이터가 없을 경우 포인터의 주소값은 None(또는 Null)이다.

노드 구조

** C/C++언어

- 노드 구조 정의

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

 

- 삽입

1) head가 NULL인 경우 -> 삽입 노드가 head

2) 리스트의 맨 처음에 삽입

3) 리스트의 노드(p) 다음에 삽입

 

ListNode* Insert(ListNode* head, ListNode* p, int data) {
	ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
	new_node->data = data;

	if (head == NULL) {		// head가 NULL인 경우, 삽입노드가 head
		head = new_node;
		new_node->next = NULL;
	}
	else if (p == NULL) {	// 리스트의 맨 처음에 삽입
		new_node->next = head;
		head = new_node;

		/*////////리스트의 맨 뒤에 삽입////////
		ListNode* temp = head;
		while (temp->next != NULL) {
			temp = temp->next;
		}
		temp->next = new_node;
		new_node->next = NULL;
		/////////////////////////////////////*/
	}
	else {					// 특정값을 가진 노드(p) 다음에 삽입
		new_node->next = p->next;
		p->next = new_node;
	}
	return head;
}

 

- 삭제

1) 리스트의 맨 처음 노드를 삭제

 

2) 리스트에서 지정된 노드(removed) 삭제

ListNode* Delete(ListNode* head, ListNode* p) {
	if (p == NULL) {	// 리스트의 맨 처음 노드 삭제
		ListNode* temp = head;
		head = head->next;
		free(temp);
	}
	else {				// 특정값을 가진 노드 삭제, p는 이전 노드
		ListNode* removed = p->next;
		p->next = removed->next;
		free(removed);
	}
	return head;
}

 

- 방문 및 검색

void Display(ListNode* head) {
	ListNode* temp = head;
	while (temp != NULL) {
		if (temp->next != NULL) {
			printf("%d -> ", temp->data);
		}
		else {
			printf("%d\n", temp->data);
		}
		temp = temp->next; 
	}
}

ListNode* Search(ListNode* head, int data) {
	ListNode* temp = head;
	while (temp != NULL) {
		if (temp->data == data) {
			return temp;
		}
		temp = temp->next;
	}
	return temp;
}

 

- 리스트 합병

ListNode* concat(ListNode* head1, ListNode* head2) {
	ListNode* temp = head1;
	if (head1 == NULL)
		return head2;
	else if (head2 == NULL)
		return head1;
	else {
		while (temp->next != NULL) {
			temp = temp->next;
		}
		temp->next = head2;
		return head1;
	}
}

 

- 역 리스트

p : 역순으로 만들 리스트

q : 역순으로 만들 노드

r : 역순으로 만들어진 리스트

ListNode* reverse(ListNode* head) {
	ListNode* p, * q, * r;
	p = head;
	q = NULL;
	while (p != NULL) {
		r = q;
		q = p;
		p = p->next;
		q->next = r;
	}
	return q;
}

 

 

- 실행 예제 소스코드 #1 (삽입, 삭제, 방문, 검색)

void main() {
	ListNode* head = NULL;

	//////////////////////삽입///////////////////////
	head = Insert(head, NULL, 10);
	head = Insert(head, NULL, 20);
	head = Insert(head, NULL, 30);
	head = Insert(head, NULL, 40);
	head = Insert(head, NULL, 50);
	Display(head);


	// 특정값 30 뒤에 삽입할 때
	ListNode* prev_node = head;
	int prev_data = 30;
	while (prev_node->data != prev_data) {
		prev_node = prev_node->next;
	}
	head = Insert(head, prev_node, 100);
	Display(head);


	//////////////////////검색///////////////////////
	int search_data = 40;
	if (Search(head, search_data) != NULL) {
		printf("특정값 %d가 존재합니다.\n", search_data);
	}
	else {
		printf("특정값 %d가 존재하지않습니다.\n", search_data);
	}

	search_data = 200;
	if (Search(head, search_data) != NULL) {
		printf("특정값 %d가 존재합니다.\n", search_data);
	}
	else {
		printf("특정값 %d가 존재하지않습니다.\n", search_data);
	}


	//////////////////////삭제///////////////////////
	head = Delete(head, NULL);
	head = Delete(head, NULL);
	Display(head);


	// 특정값 100 삭제할 때
	prev_node = head;
	prev_data = 100;
	while (prev_node->next->data != prev_data) {
		prev_node = prev_node->next;
	}
	head = Delete(head, prev_node);
	Display(head);
}

    50 -> 40 -> 30 -> 20 -> 10
    50 -> 40 -> 30 -> 100 -> 20 -> 10
    특정값 40가 존재합니다.
    특정값 200가 존재하지않습니다.
    30 -> 100 -> 20 -> 10
    30 -> 20 -> 10

 

- 실행 예제 소스코드 #2 (리스트 합병)

void main() {
	ListNode* head1 = NULL;
	head1 = Insert(head1, NULL, 10);
	head1 = Insert(head1, NULL, 20);
	head1 = Insert(head1, NULL, 30);
	head1 = Insert(head1, NULL, 40);
	head1 = Insert(head1, NULL, 50);
	Display(head1);

	ListNode* head2 = NULL;
	head2 = Insert(head2, NULL, 60);
	head2 = Insert(head2, NULL, 70);
	head2 = Insert(head2, NULL, 80);
	head2 = Insert(head2, NULL, 90);
	head2 = Insert(head2, NULL, 100);
	Display(head2);

	head1 = concat(head1, head2);
	Display(head1);
}

    50 -> 40 -> 30 -> 20 -> 10
    100 -> 90 -> 80 -> 70 -> 60
    50 -> 40 -> 30 -> 20 -> 10 -> 100 -> 90 -> 80 -> 70 -> 60

 

- 실행 예제 소스코드 #3 (역 리스트)

void main() {
	ListNode* head = NULL;
	head = Insert(head, NULL, 10);
	head = Insert(head, NULL, 20);
	head = Insert(head, NULL, 30);
	head = Insert(head, NULL, 40);
	head = Insert(head, NULL, 50);
	Display(head);

	head = reverse(head);
	Display(head);
}

    50 -> 40 -> 30 -> 20 -> 10
    10 -> 20 -> 30 -> 40 -> 50

 

 

** Python

- 노드 구조 정의

class ListNode:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next