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

단일 연결리스트(Singly Linked List)

단일 연결리스트란 단일 방향(포인터)을 가진 리스트를 말한다. 포인터를 이용해 다음 순서의 노드를 가리켜주고, 이를 통해 머리부터 끝까지 탐색을 돌 수 있다.

<소스코드>

?

1 2 3 4 5 6 7 8 9 10

class Node { public:     int data;     Node *next;     Node() {}     Node(int data) : data(data) { //노드를 생성할 때 매개변수 값을 data변수에 값을 대입시켜준다.         this->next = NULL; // next포인터를 초기화 시켜준다.     }     ~Node() {} };

단일 연결리스트의 노드의 구성은 data와 다음 노드를 가리키는 next 포인터 두 가지가 있다. 예제는 단순히 데이터를 int형 변수 하나를 사용했지만 구조체를 활용해서 좀 더 다양한 자료형을 담을 수도 있다.

리스트는 그림과 같은 구조로 이뤄져 있다.  단일 방향이기 때문에 특정 방향으로만 타고 들어가 모든 정보를 찾아갈 수 있다. 리스트를 접근하기 위해 기준이 되는 노드를 머리(Head)라고 설정해 놓는다.

즉, head 포인터를 기준으로 next 포인터를 통해서 다음 데이터를 순차적으로 접근이 가능하다.

노드가 생성될 때 next 포인터가 null로 초기화 해주고, 구현 중에  null 포인터를 참조하면 error가 날 수 있으니 주의해야한다.

 

단일연결리스트 구현에 있어서 대표적(?)으로 필요한 함수는 데이터 삽입, 수정, 삭제, 출력이 있다.

[데이터 삽입]

 <소스코드>

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

//삽입 void addNode(int data) {       Node *newNode = new Node(data); //새로운 노드를 생성해준다.     size++; //현재 노드의 개수           if (head == NULL) { //머리노드가 아무것도 없는 상태라면         head = newNode;     }     else {         Node* cur = head;         while (cur) {             if (cur->next == NULL) { //cur의 다음노드가 비었다면                 cur->next = newNode; //새로운 노드를 연결해준다.                 break;             }             cur = cur->next;  //다음노드로 이동         }     } }

우선 적으로 내가 구현한 리스트는 가장 마지막 순서에 새로운 노드를 넣는다. 처음 head가 비어있는 상태라면 head에 새로운 노드를 넣어주고, 이미 노드가 존재한다면 그 다음 순서에 넣어준다.

리스트를 다음 노드로 이동하는 것을 그림으로 나타내면 이해하기 쉽다. 포인터를 이용해 노드를 껑충껑충 뛰면서 이동한다고 생각하면 된다.

[데이터 수정]

  <소스코드>

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14

//수정 void changeNode(int N, int data) { //매개변수-변경하려는 노드순서번호/데이터       if (N <= 0 || N > size) {         printf("해당노드가 없습니다.\n");         return;     }       Node* cur = head;     for (int i = 1; i < N; i++) cur = cur->next;  //다음노드로 이동       cur->data = data;     return; }

이 함수는 변경하려는 노드 번호와 변경 데이터를 매개변수로 받고, 해당 노드 번호를 찾아서 데이터르 변경해주는 기능을 한다. 

초기 조건은 노드번호가 현재 노드 정보 개수보다 많거나 적으면 해당 노드가 없다고 출력해준다.

[데이터 삭제]

 <소스코드>

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

//삭제     void deleteNode(int N) {//매개변수-삭제하려는 노드순서번호           if (N <= 0 || N > size) {             printf("해당노드가 없습니다.\n");             return;         }           Node* cur = head;         Node* pre = NULL;           for (int i = 1; i < N; i++) {             pre = cur;             cur = cur->next;  //다음노드로 이동         }           size--; //삭제하기 때문에 노드 개수를 줄여준다.           if (N == 1) head = head->next;         else pre->next = cur->next; //삭제될 노드를 제외하고 포인터를 연결해준다.                   delete cur;  //n번째 노드삭제           return;     }

이 함수는 해당 노드 번호(순서)를 매개변수로 받으면 해당 순서의 노드를 삭제하는 기능을한다.

삭제는 cur변수와 함께 이전 노드를 가리키는 pre포인터가 필요하다. 현재노드를 지우고, 이전노드의 next포인터를 cur의 next포인터로 연결시켜주면 매듭이 다시 만들어진다. 그 이후에 현재 노드를 삭제한다.

[데이터 출력]

  <소스코드>

?

1 2 3 4 5 6 7 8 9 10

//출력 void printList() {     Node* cur = head;     while (cur) {         printf("%d ", cur->data);         cur = cur->next;  //다음노드로 이동     }     printf(": 총 %d 개\n",size);//노드 개수 출력하기     return; }

다음 출력은 while문을 통해서 null값을 만나면, 즉 마지막 노드까지 도달할 때까지 돌면서 데이터를 출력해주면 된다.

[예제]

<전체소스코드>

	#include <cstdio>
	#include <iostream>
	using namespace std;
	class Node {
	public:
	int data;
	Node *next;
	Node() {}
	Node(int data) : data(data) { //노드를 생성할 때 매개변수 값을 data변수에 값을 대입시켜준다.
	this->next = NULL; // next포인터를 초기화 시켜준다.
	}
	~Node() {}
	};
	class LinkedList {
	public:
	Node *head;
	int size = 0;
	LinkedList() {
	head = NULL;
	}
	//삽입
	void addNode(int data) {
	Node *newNode = new Node(data); //새로운 노드를 생성해준다.
	size++; //현재 노드의 개수
	if (head == NULL) { //머리노드가 아무것도 없는 상태라면
	head = newNode;
	}
	else {
	Node* cur = head;
	while (cur) {
	if (cur->next == NULL) { //cur의 다음노드가 비었다면
	cur->next = newNode; //새로운 노드를 연결해준다.
	break;
	}
	cur = cur->next; //다음노드로 이동
	}
	}
	}
	//출력
	void printList() {
	if (head == 0)printf("빈 리스트 ");
	Node* cur = head;
	while (cur) {
	printf("%d ", cur->data);
	cur = cur->next; //다음노드로 이동
	}
	printf(": 총 %d 개\n\n", size);//노드 개수 출력하기
	return;
	}
	//수정
	void changeNode(int N, int data) { //매개변수-변경하려는 노드순서번호/데이터
	if (N <= 0 || N > size) {
	printf("해당노드가 없습니다.\n");
	return;
	}
	Node* cur = head;
	for (int i = 1; i < N; i++) cur = cur->next; //다음노드로 이동
	printf("변경전 : "); printList();
	cur->data = data;
	printf("변경후 : "); printList();
	return;
	}
	//삭제
	void deleteNode(int N) {//매개변수-삭제하려는 노드순서번호
	if (N <= 0 || N > size) {
	printf("해당노드가 없습니다.\n");
	return;
	}
	Node* cur = head;
	Node* pre = NULL;
	for (int i = 1; i < N; i++) {
	pre = cur;
	cur = cur->next; //다음노드로 이동
	}
	printf("삭제전 : "); printList();
	size--; //삭제하기 때문에 노드 개수를 줄여준다.
	if (N == 1) head = head->next;
	else pre->next = cur->next; //삭제될 노드를 제외하고 포인터를 연결해준다.
	delete cur; //n번째 노드삭제
	printf("삭제후 : "); printList();
	return;
	}
	};
	int main() {
	LinkedList list;
	//삽입
	list.printList();
	for (int i = 1; i <= 10; i++)list.addNode(i);
	list.printList();
	//수정
	list.changeNode(2, 10);
	list.changeNode(5, 15);
	//삭제
	list.deleteNode(6);
	list.deleteNode(7);
	}

view rawSinglyLinkedList_Test.cpp hosted with ❤ by GitHub

<출력화면>

출처 : http://meylady.tistory.com