[C++] 연결리스트 Linked list 코드 구현 방법

 

이 포스트에서는 단일연결 리스트를 C++ 코드로 구현하는 방법을 다룬다.

 

리스트가 뭘까?

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

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

그럼 배열과 리스트의 차이는?

배열은 인덱스로 표현되는 '순서'가 배열 원소의 메모리 공간에서 물리적 의미를 의미하는 데 반해서,

리스트의 '순서' 개념은 어떤 정의에 의해 결정된 '논리적인 순서'다. 원소들의 물리적인 저장 순서나 위치와 무관하게 원소들 간의 논리적인 순서만 유지한다.

 

리스트의 구현 방법에는 두 가지가 있다.

1) 포인터를 이용한 방법, 2) 배열을 이용한 방법.

1) 포인터를 이용한 방법

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

2) 배열을 이용한 방법

배열을 만들어놓고 중간에 데이터를 삽입하려면 삽입하려는 위치 뒤에 있는 데이터를 다 한 칸씩 뒤로 밀고 삽입해야 한다는 엄청난 단점이 있다. 삭제할 때도 삭제하려는 위치 뒤에 있는 데이터를 한 칸씩 앞으로 땡겨야 한다. 이러한 동작들은 원소의 수에 비례해서 프로그램 수행 시간을 엄청나게 증가시킬 수 있다.

 

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

본격적으로 리스트 구현을 하기 위한 기본 개념들을 잡고 가보자.

 

노드

노드(node)는 '리스트의 원소(값)'과 '다음 원소를 가리키는 정보'로 구성되어 있다.

노드는 데이터 요소인 (원소, 값)과 리스트의 다음 원소를 지시하는 포인터(주소, 링크)로 구성된다.

값 (데이터)

메모리 주소값 (포인터)

포인터에는 가리키는 값의 주소가 저장된다.

 

연결리스트 생성

struct linked_list_node {
    int data;
    struct linked_list_node *link;
};

 

연결리스트 노드 삽입&삭제

→ 리스트의 원소 삭제 연산

1. 삭제할 노드의 선행 노드의 링크 필드를 삭제할 노드의 후행 노드를 가리키게 한다.
2. 삭제할 노드를 메모리에 반환한다.

 

→ 리스트의 원소 삽입 연산

1. 메모리 공간을 할당받고 삽입할 내용을 저장하여 삽입할 노드를 생성한다.
2. 삽입할 노드의 링크부분이 후행 노드가 될 노드를 가리키게 한다.
3. 삽입될 노드의 선행 노드가 될 노드의 링크 필드가 삽입할 노드의 주소를 가리키게 한다.

void addNode(linkedList_h* H, int x){
  listNode* NewNode;
  listNode* LastNode;
  NewNode = (listNode*)malloc(sizeof(listNode));
  NewNode -> data = x;
  NewNode -> link = NULL;
}

만약 연결 리스트의 마지막에 삽입하고 싶을 땐 아래와 같이 한다.

void addNode(linkedList_h* H, int x){
   if(H -> head == NULL) {
   		H -> head = NewNode;
        return;
   }
   LastNode = H -> head;
   while(LastNode -> link != NULL)
   		LastNode = LastNode -> link;
   LastNode -> link = NewNode;
}

 

 

최종 단일연결리스트 코드는 아래와 같이 2가지로 구성되어 있다. 

singlist라는 클래스와 노드 구조를 선언하고 있는  Linkedlist.h 파일과

연결리스트를 구현할 main 함수가 들어있는 singlistMian.cpp 파일이다.

먼저 Linkedlist.h 코드는 다음과 같다.

#pragma once
#include <iostream>
using namespace std;

struct Node {
	int data;
	struct Node* link; // 이 구조체 자체를 가리키는 포인터이므로 struct으로 선언
};

struct HeadNode {
	Node* head; // Node를 가리키는 포인터, head
};

class Singlist {

public:
	/*리스트 생성, 헤드노드 */
	HeadNode* createList() {
		HeadNode* H = new HeadNode; // HeadNode를 가리키는 포인터, H
		H->head = NULL;
		return H;
	}
	
	/* 리스트의 마지막에 노드 삽입*/
	void addNode(HeadNode* H, int x) { 
		Node* NewNode = new Node;  //새로 만들 노드 
		Node* LastNode; //원래 있던 노드의 마지막 노드
		NewNode->data = x;
		NewNode->link = NULL;

		if (H->head == NULL) { // 리스트가 비어있을 경우
			H->head = NewNode;
			return;
		}

		LastNode = H->head;   // 리스트가 비어있지 않은 경우에 연결리스트의 가장 처음 노드가 LastNode를 가리키게 한다.
		while (LastNode->link != NULL) LastNode = LastNode->link; // 연결리스트의 마지막 노드를 찾는 과정
		LastNode->link = NewNode; // 마지막 노드를 찾고 while문을 나오면 뒤에 새 노드를 가리키게 한다.
	}

	/* 리스트의 마지막 노드 삭제*/
	void deleteNode(HeadNode* H) {  
		Node* prevNode;  // 삭제되는 노드의 앞 노드
		Node* delNode;  // 삭제되는 노드

		if (H->head == NULL) return; // 리스트가 빈 경우
		if (H->head->link == NULL) { // 한 개의 노드만 가진 경우
			delete H->head;  // head가 가리키던 메모리 공간을 힙 영역에 반환
			H->head = NULL;  // 헤드 노드의 link 부분인 head를 null로 설정.
			return;
		}
		else {  // 리스트에 노드 여러 개 있는 경우
			prevNode = H->head; // 헤드 노드가 가리키는 노드가 prevNode가 되게 설정
			delNode = H->head->link; // prevNode 다음 위치로 delNode 설정
			while (delNode->link != NULL) { //delNode가 마지막노드가 될 때까지
				prevNode = delNode;       // prevNode를 한칸씩 가고
				delNode = prevNode->link; // delNode도 한칸씩 끝으로 간다.
			}
			free(delNode);  // 마지막 노드의 메모리 공간을 반환
			prevNode->link = NULL;
		}
	}

	/* 리스트의 특정 노드 삭제*/
	void deleteThisNode(HeadNode* H, int deldata) {
		Node* delNode;  // 삭제하려는 노드
		Node* prevNode; // 삭제하려는 노드의 앞 노드
		prevNode = H->head;

		while (prevNode->link->data != deldata) {
			prevNode = prevNode->link;
		}

		delNode = prevNode->link;   // prevNode가 가리키는 노드가 삭제할 노드
		prevNode->link = delNode->link;  // prevNode가 delNode 다음 노드를 가리키도록
		free(delNode);  // delNode 삭제

		cout << deldata << " 데이터 값을 가진 노드가 삭제됐습니다." << endl;
		return;
	}

	/* 리스트에 특정 노드 삽입*/
	void addThisNode(HeadNode* H, int afterthisdata, int adddata) {
		// afterthisdata: 이 데이터 뒤에 삽입하고 싶소.
		// adddata: 이 데이터를 삽입하고 싶소.

		Node* prevNode;  //삽입하려는 노드의 이전 노드
		prevNode = H->head;

		while (prevNode->data != afterthisdata) {
			prevNode = prevNode->link;
		}

		Node* NewNode = new Node;
		NewNode->data = adddata;
		NewNode->link = prevNode->link;
		prevNode->link = NewNode;
		return;
	}

	/* 리스트의 특정 노드 검색*/
	void searchNode(HeadNode* H, int thisdata) {
		Node* someNode;
		someNode = H->head;

		while (someNode->data != thisdata) {
			someNode = someNode->link;
		}
		cout << thisdata << " 데이터를 검색하는 데 성공했습니다." << endl;
	}

	/* 연결리스트 출력*/
	void printList(HeadNode* L) {
		//노드 순서대로 리스트 출력
		Node* p;
		cout << "연결리스트 목록 = ( ";
		p = L->head;

		while (p != NULL) {
			cout << p->data;
			p = p->link;
			if(p != NULL) cout << " --> ";
		}
		cout << " )" << endl;
	}
};

 

singlistMian.cpp 코드는 아래와 같다.

#include <iostream>
#include "Linkedlist.h"
using namespace std;

void main()
{
	Singlist list;
	HeadNode* L;
	L = list.createList();

	cout << "1. 빈 연결 리스트를 생성했습니다." << endl << endl;

	int data1, data2, data3;
	cout << "2. 연결 리스트에 추가할 노드의 데이터를 3개 정해주세요: ";
	cin >> data1 >> data2 >> data3;
	list.addNode(L, data1);
	list.printList(L);
	list.addNode(L, data2);
	list.printList(L);
	list.addNode(L, data3);
	list.printList(L);
	cout << endl;

	cout << "3. 탐색할 노드의 데이터를 정해주세요 : ";
	int data4;
	cin >> data4;
	list.searchNode(L, data4);

	cout << endl;
	cout << "4-1. 어떤 노드 뒤에 노드를 추가할건가요? ";
	int data5, data6;
	cin >> data5;
	cout << "4-2. 그 노드 뒤에 어떤 데이터를 가진 노드를 추가할건가요? ";
	cin >> data6;
	list.addThisNode(L, data5, data6);
	list.printList(L);
	cout << endl;

	cout << "5. 삭제하고자 하는 노드를 알려주세요 : ";
	int data7;
	cin >> data7;
	list.deleteThisNode(L, data7);
	list.printList(L);
	cout << endl;

	cout << "6. 마지막 노드를 삭제합니다." << endl;
	list.deleteNode(L);
	list.printList(L);
	cout << endl;

	cout << "피곤하니까 연산을 끝내겠습니다." << endl;

}

 

출력결과는 다음과 같다.

 

연결리스트의 응용인 이중연결리스트와 원형연결리스트에 알아보고 싶은 분들은 아래 포스트를 참고하세요.

2020/09/10 - [Programming/Data Structure] - [C++] 이중연결리스트 코드 구현 방법 Double linked list

[C++] 이중연결리스트 코드 구현 방법 Double linked list

2020/09/11 - [Programming/Data Structure] - [C++] 원형 연결 리스트 코드 구현 방법 Circular linked list

[C++] 원형 연결 리스트 코드 구현 방법 Circular linked list