[#1] Singly Linked List

배열처럼 데이터들의 집합 기능을 가지면서 크기가 고정적이지 않고 동적으로 관리가 가능한 리스트를 구현하려고 한다. 이중 자료구조의 기본이 되는 Singly Linked List를 구현해보았다. 그리고 개인적으로 유지보수하며 프로젝트에 활용하기 위해 템플릿으로 구현해보았다. Double Linked List와 Circular Linked List는 기존 Linked List와 구조상 크게 다르지 않고 각 포인터에 대한 연결 지점을 다르게 엮는 정도이므로 따로 포스팅하지 않을 계획이다. 

 

 

 

---

목차

• 관련용어
• 링크드 리스트의 주요 기능
• Singly Linked List의 구현
• 전체 코드

 

---

관련 용어

 

링크드 리스트(Linked List)를 구현하면서 자료구조에서 사용되는 단어들이 등장한다.

그 단어들의 의미는 다음과 같다.

 

• Linked List: 각 노드들을 연결해서 만드는 리스트
• Node: 마디를 뜻하며, 데이터를 직접적으로 관리하는 구조체 또는 클래스를 의미한다. 
• Head: 링크드 리스트에서 가장 첫 부분에 있는 노드의 주소를 담는 포인터이다. 
• Tail: 링크드 리스트에서 가장 마지막 부분에 있는 노드의 주소를 담는 포인터이다.
• Static Memory(정적 메모리): 전역변수나 정적 지역 변수가 저장되는 영역, 프로그램이 종료될 때 회수
• Free Memory(자유 저장소): 동적으로 할당된 메모리들이 저장되는 영역, 프로그래머가 관리하는 공간, 각 Scope 영역에 따라 회수
• Automatic Memory(자동 메모리): 지역 변수들이 저장되는 영역, 각 Scope 영역에 따라 회수

 

Linked List의 장점

다뤄야할 데이터들의 크기를 동적으로 활용할 수 있다는 점에서 매우 다양하게 사용되는 자료구조이다. 데이터가 늘어날 때마다 노드를 만들어서 Tail의 포인터로 가리키면 크기 제한없이 사용이 가능한 이점이 있다.

 

Linked List의 단점

배열은 인덱스 번호만 알면 그 데이터에 바로 접근 하는게 가능하다. 하지만 링크드 리스트는 중간에 삽입된 데이터에 접근하려면 각 노드를 건너건너 넘어가서 데이터를 찾아야한다. 최악의 경우 n번의 경우로 데이터를 찾아내게 될 수도 있다. 

 

---

 

링크드 리스트의 주요 기능

링크드 리스트를 표현하기 위해 구현해야할 주요 기능이 총 5가지가 있다.

 

• 노드 생성/소멸
  노드의 공간을 할당해주고 생성하는 함수 or 노드가 가진 공간을 회수하는 소멸 함수
• 노드 추가
  노드 생성/소멸 함수를 이용해서 클래스에 노드를 생성하고 Head포인터와 Tail포인터를 설정해준다.
• 노드 탐색
  요청된 데이터에 해당하는 노드를 탐색한다.
• 노드 삭제
  사용자가 삭제를 원하는 노드를 삭제하는 연산을 한다.
• 노드 삽입
  사용자가 삽입을 원하는 노드를 삽입하는 연산을 한다.

 

---

 

Singly Linked List의 구현

Singly Linked List란 한쪽 방향으로만 엮여있는 리스트를 의미한다. Double Linked List는 각 노드의 앞뒤를 모두 엮여놓았기 때문에 양방향 탐색이 가능하지만 Singly Linked List는 한방향 탐색만 가능하기 때문에 붙여진 명칭이다.

 

노드 생성

		Node CreateNode(T* newData)
		{
			Node newNode = new tagNode;     // 노드 생성
			newNode->addData(newData);         // 새로운 값 대입
			count++;                           // 노드 개수 카운트
			return newNode;
		}

 

각 노드에 대한 힙 공간을 할당해준 후 새로운 데이터를 노드에 보관한 후 노드 Count를 세고 생성된 노드의 주소를 반환한다. 템플릿 특성상 외부에서 접근할 수 없게해야하므로 클래스의 protected 부분에 위치해 있다.

 

노드 추가 

	template <typename T>
	bool SLL<T>::AppendData(T* newData)
	{
		// 헤드 노드가 nullptr일 경우 새로운 head로 지정
		bool isDone = false;
		if (head == nullptr)
		{
			head = CreateNode(newData);
			isDone = true;
		}
		else
		{
			tail = head;
			while (tail->nextNode != nullptr)
				tail = tail->nextNode;
			tail->nextNode = CreateNode(newData);
			isDone = true;
		}
		return isDone;
	}

 

head포인터가 nullptr일 경우 새로운 노드를 head포인터로 가리키고 head가 nullptr이 아닐 경우 새로운 노드를 만든 후 tail 포인터로 가리킨다.

 

 

노드 삭제

	template <typename T>
	bool SLL<T>::DeleteData(size_t num)
	{
		bool isDone = false;
		if (num > 0 && num < count - 1)             // Head와 Tail을 제외한 노드 제거
		{
			Node current = head;
			for (int i = 0; i < num - 1; i++)       // 지우려는 노드 이전 노드 탐색
				current = current->nextNode;
			Node temp = current->nextNode;                    // 지우려는 노드를 temp에 보관
			current->nextNode = current->nextNode->nextNode;  // 이전 노드의 꼬리를 다다음 노드로 가리킨다.
			delete temp;                            // 지우려던 노드 delete
			isDone = true;
		}
		else if (num == 0)
		{
			Node temp = head;
			head = head->nextNode;
			delete temp;
			isDone = true;
		}
		else if (num == count - 1)
		{
			Node current = head;
			for (int i = 0; i < num - 1; i++)       // 지우려는 노드 이전 노드 탐색
				current = current->nextNode;
			Node temp = current->nextNode;          // 지우려는 노드를 temp에 보관
			tail = current;              // 이전 노드를 tail로 가리킨다
			tail->nextNode = nullptr;    // 마지막 노드이기 때문에 다음 노드를 nullptr로 바꾼다.
			delete temp;                 // 삭제하려던 노드를 메모리 해제 시킨다.
			isDone = true;
		}
		else
			std::cout << "삭제하는데에 문제가 발생했습니다" << std::endl;
		if (isDone) --count;
		return isDone;
	}

 

이전 지우려는 노드의 이전 노드를 탐색한 후 nextNode가 가리키는 노드를 지우려던 노드의 앞노드를 가리키게 한다.

if문이 불필요하게 많아진거 같아서 좀 더 나은 로직이 있는지 앞으로 검토해볼 생각이다.

 

 

 

노드 탐색

template <typename T>
	T& SLL<T>::operator[](size_t num)
	{
		if (num >= 0 && num < count)
		{
			Head tHead = head;
			for (int i = 0; i < num; i++)
				tHead = tHead->nextNode;
			return *((*tHead).data);
		}
		else
			std::cout << "유효하지 않은 인덱스 번호" << std::endl;
		
		// data에 아무것도 없을 경우
		std::cout << this << " is Empty" << std::endl;
	}

 

배열 처럼 동작하고 템플릿 클래스의 특성상 어떠한 자료에 대한 탐색 요청이 들어올 지 몰라서 인덱스 오버로딩을 활용해서 탐색 기능 대신 배열 인덱스 동작과 유사하게 구현했다. 해당 인덱스에 해당하는 노드를 Count 변수를 이용해 탐색한 후 그 노드의 값을 반환한다. 배열의 인덱스처럼 반환된 값을 사용자가 바꿀 수도 있다.

 

 

  노드 삽입

	template <typename T>
	bool SLL<T>::InsertData(T* newData, size_t num)
	{
		bool isDone = false;
		if (count == 0)
			std::cout << this << " is Empty" << std::endl;
		if (num == 0)
		{
			Node temp = head;
			head = CreateNode(newData);
			head->nextNode = temp;
			isDone = true;
		}
		else if (num > 0 && num < count)
		{
			Head tHead = head;
			for (int i = 0; i < num - 1; i++)
				tHead = tHead->nextNode;    // 추가를 원하는 위치의 노드 이전 항을 찾는다
			Node temp = tHead->nextNode;    // 다음 노드를 temp에 보관
			tHead->nextNode = CreateNode(newData);  // 이전 항에 새로운 노드를 만들어서 가리킨다. 
			tHead->nextNode->nextNode = temp;    // 보관해두었던 노드를 새로운 항의 다음 newNode로 가리킨다.
			isDone = true;
		}
		if (!isDone)
			std::cout << "인덱스 범위 초과" << std::endl;
		return isDone;
	}

 

원하는 위치에 노드를 삽입할 수 있게한다. 해당 위치 이전의 노드를 새로운 데이터에 대한 노드를 생성해 가리키게 한 후 기존에 위치해있던 노드를 뒤로 밀어낸 후 새로운 노드로 가리키게 한다.

 

 

소멸자

	template <typename T>
	SLL<T>::~SLL()
	{
		// head의 다음 노드를 맡겼다가 자신의 데이터를 삭제하는 방식
		// 다시 그 다음 노드를 temp로 부터 되돌려받으므로 자신이 null이면 종료한다
		while (head != nullptr)
		{
			Head tHead = head->nextNode;
			delete head;
			head = tHead;
		}
	}

 

각 노드에 대한 데이터 공간을 해제해주기 위해서 head 포인터를 시작으로 다음 노드들을 순차적으로 소멸시킨다.

 

---

 

전체 코드

 

Singly Linked List의 헤더파일에 대한 모든 코드

// Linked List 2022.06.22 푸바오
#ifndef __LINKED_LIST_H__
#define __LINKED_LIST_H__

#include <iostream>
#include <cstdlib>

namespace FB
{
	/* Singly Linked List Class */
	template <typename T = int>
	class SLL
	{
	protected:
		/* tagNode 내포 클래스 영역*/
		class tagNode
		{
		public:
			T*          data;        // 데이터 값
			tagNode*    nextNode;    // 다음 노드
			tagNode() : data(nullptr) { nextNode = nullptr; }
			void addData(T* data)
			{
				this->data = data;
			}
		};
		typedef tagNode* Head;
		typedef tagNode* Node;
		/* Node 생성*/
		Node CreateNode(T* newData)
		{
			Node newNode = new tagNode;     // 노드 생성
			newNode->addData(newData);         // 새로운 값 대입
			count++;                           // 노드 개수 카운트
			return newNode;
		}
	public:
		/* 생성자 or 소멸자*/
		explicit SLL() : count(0) { head = nullptr; tail = nullptr; }
		~SLL();
		/* Node 개수 반환*/
		size_t size() { return count; }
		/* Node 추가, 삭제*/
		bool AppendData(T* newData);
		bool DeleteData(size_t num);
		/* Node와 Node사이에 추가 */
		bool InsertData(T* newData, size_t num);
		/* Node 탐색*/
		T& operator[] (size_t num);
	private:
		Head        head;        // 헤드 포인터
		Node        tail;        // 노드 리스트
		size_t      count;       // 노드의 개수
	};

	template <typename T>
	bool SLL<T>::AppendData(T* newData)
	{
		// 헤드 노드가 nullptr일 경우 새로운 head로 지정
		bool isDone = false;
		if (head == nullptr)
		{
			head = CreateNode(newData);
			isDone = true;
		}
		else
		{
			tail = head;
			while (tail->nextNode != nullptr)
				tail = tail->nextNode;
			tail->nextNode = CreateNode(newData);
			isDone = true;
		}
		return isDone;
	}
	
	template <typename T>
	bool SLL<T>::DeleteData(size_t num)
	{
		bool isDone = false;
		if (num > 0 && num < count - 1)             // Head와 Tail을 제외한 노드 제거
		{
			Node current = head;
			for (int i = 0; i < num - 1; i++)       // 지우려는 노드 이전 노드 탐색
				current = current->nextNode;
			Node temp = current->nextNode;                    // 지우려는 노드를 temp에 보관
			current->nextNode = current->nextNode->nextNode;  // 이전 노드의 꼬리를 다다음 노드로 가리킨다.
			delete temp;                            // 지우려던 노드 delete
			isDone = true;
		}
		else if (num == 0)
		{
			Node temp = head;
			head = head->nextNode;
			delete temp;
			isDone = true;
		}
		else if (num == count - 1)
		{
			Node current = head;
			for (int i = 0; i < num - 1; i++)       // 지우려는 노드 이전 노드 탐색
				current = current->nextNode;
			Node temp = current->nextNode;          // 지우려는 노드를 temp에 보관
			tail = current;              // 이전 노드를 tail로 가리킨다
			tail->nextNode = nullptr;    // 마지막 노드이기 때문에 다음 노드를 nullptr로 바꾼다.
			delete temp;                 // 삭제하려던 노드를 메모리 해제 시킨다.
			isDone = true;
		}
		else
			std::cout << "삭제하는데에 문제가 발생했습니다" << std::endl;
		if (isDone) --count;
		return isDone;
	}

	template <typename T>
	bool SLL<T>::InsertData(T* newData, size_t num)
	{
		bool isDone = false;
		if (count == 0)
			std::cout << this << " is Empty" << std::endl;
		if (num == 0)
		{
			Node temp = head;
			head = CreateNode(newData);
			head->nextNode = temp;
			isDone = true;
		}
		else if (num > 0 && num < count)
		{
			Head tHead = head;
			for (int i = 0; i < num - 1; i++)
				tHead = tHead->nextNode;    // 추가를 원하는 위치의 노드 이전 항을 찾는다
			Node temp = tHead->nextNode;    // 다음 노드를 temp에 보관
			tHead->nextNode = CreateNode(newData);  // 이전 항에 새로운 노드를 만들어서 가리킨다. 
			tHead->nextNode->nextNode = temp;    // 보관해두었던 노드를 새로운 항의 다음 newNode로 가리킨다.
			isDone = true;
		}
		if (!isDone)
			std::cout << "인덱스 범위 초과" << std::endl;
		return isDone;
	}

	template <typename T>
	T& SLL<T>::operator[](size_t num)
	{
		if (num >= 0 && num < count)
		{
			Head tHead = head;
			for (int i = 0; i < num; i++)
				tHead = tHead->nextNode;
			return *((*tHead).data);
		}
		else
			std::cout << "유효하지 않은 인덱스 번호" << std::endl;
		
		// data에 아무것도 없을 경우
		std::cout << this << " is Empty" << std::endl;
	}

	/* 소멸자 */
	template <typename T>
	SLL<T>::~SLL()
	{
		// head의 다음 노드를 맡겼다가 자신의 데이터를 삭제하는 방식
		// 다시 그 다음 노드를 temp로 부터 되돌려받으므로 자신이 null이면 종료한다
		while (head != nullptr)
		{
			Head tHead = head->nextNode;
			delete head;
			head = tHead;
		}
	}
}
#endif

 

 

 

int main()을 이용한 간단한 테스트 케이스

#include <iostream>
#include "LinkedList.h"

int main(void)
{
	using namespace std;
	FB::SLL<int> test;

	int nA = 30;
	int nB = 20;
	test.AppendData(&nA);
	test.AppendData(&nB);
	for (int i = 0; i < test.size(); i++)
		cout << test[i] << endl;

	cout << endl;
	test.InsertData(&nB, 0);
	test.InsertData(&nB, 0);
	test.InsertData(&nB, 0);
	test.InsertData(&nB, 0);
	for (int i = 0; i < test.size(); i++)
		cout << test[i] << endl;

	return 0;
}

 

 

---