Linked List 구현하기

🍋 Linked List란?

연결 리스트, 링크드 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 자료 추가와 삭제는 O(1)으로 빠르지만, 데이터를 탐색할 때 O(n)으로 많은 시간이 소요 된다.

연결 리스트의 종류로는 단일 연결 리스트, 이중 연결 리스트 등이 있다.

세 개의 정수를 저장하고 있는 연결 리스트

🍓노드 클래스 구현

Node.h

#pragma once

class Node
{
public:
	explicit Node();
	virtual ~Node() = default;

	void SetData(int data);
	int GetData();
	void SetNext(Node* pointer);
	Node* GetNext();
	void visit();

private:
	int _data = 0;
	Node* _nextPointer = nullptr;
};

Node.cpp

#include "Node.h"
#include <iostream>
#include <string>

Node::Node()
{
}

void Node::SetData(int data)
{
	_data = data;
}

int Node::GetData()
{
	return _data;
}

void Node::SetNext(Node* pointer)
{
	_nextPointer = pointer;
}

Node* Node::GetNext()
{
	return _nextPointer;
}

void Node::visit()
{
	std::cout << std::to_string(_data) << std::endl;
}

실제 사용할 데이터를 int형으로 해줬고, 다음 노드 주소는 Node*형으로 했다. 새로운 노드를 만들 때 외부에서 값을 넘겨 줄 수 있게 getter setter도 만들어 준다.

🍓메인Cpp 만들기

링크드 리스트의 시작 헤더 만들기

#include "Node.h"

Node* pHeader = nullptr;

int main()
{

	return 0;
}

링크드 리스트의 시작 주소를 가지는 헤더를 만들어 준다.

새로운 노드 넣기

void PushBack(int data)
{
	if (pHeader == nullptr)
	{
		Node* pNode = nullptr;

		pNode = new Node;

		if (pNode != nullptr)
			pNode->SetData(data);

		pHeader = pNode;

		return;
	}

	Node* pCur = pHeader;

	while (pCur->GetNext() != nullptr)
	{
		pCur = pCur->GetNext();
	}

	Node* pNode = nullptr;

	pNode = new Node;

	if (pNode != nullptr)
		pNode->SetData(data);

	pCur->SetNext(pNode);
	return;
}

헤더가 비어 있으면 새로운 노드를 생성하고 주소 값을 헤더에 넣는다. 다른 노드가 있다면, 마지막 노드의 nextPointer에 새로 생성한 노드의 주소를 넣는다.

노드 삭제하기

void Delete(int data)
{
	if (pHeader == nullptr)
	{
		std::cout << "Empty" << std::endl;
		return;
	}

	if (pHeader->GetData() == data)
	{ 
		Node* pDelete = pHeader;
		pHeader = pHeader->GetNext();
		delete pDelete;
		return;
	}

	Node* pCur = pHeader;
	Node* pPre = nullptr;

	while (pCur!= nullptr)
	{
		if (pCur->GetData() == data)
		{
			Node* pDelete = pCur;
			Node* pCurNext = pDelete->GetNext();
			pPre->SetNext(pCurNext);
			delete pDelete;
			return;
		}
		else
		{
			pPre = pCur;
			pCur = pCur->GetNext();
		}
	}
}

순회하면서 같은 데이터를 만나면 삭제하게 구현했다. 이전 노드의 NextPointer에 삭제할 노드의 NextPoint를 넣고 삭제할 노드를 지워준다.

전체 순회 만들기

void VisitAll()
{
	if (pHeader == nullptr)
	{
		std::cout << "Empty" << std::endl;
		return;
	}

	Node* pCur = pHeader;

	while (pCur != nullptr)
	{
		std::cout << std::to_string(pCur->GetData()) + " ";
		pCur = pCur->GetNext();
	}
}

순회할 때 현재 노드가 nullptr일 때 까지 순회하며 데이터를 보여 준다.

메인Cpp 전체 코드

#include "Node.h"
#include <iostream>
#include <string>
#include "Windows.h"

Node* pHeader = nullptr;

void PushBack(int data)
{
	if (pHeader == nullptr)
	{
		Node* pNode = nullptr;

		pNode = new Node;

		if (pNode != nullptr)
			pNode->SetData(data);

		pHeader = pNode;

		return;
	}

	Node* pCur = pHeader;

	while (pCur->GetNext() != nullptr)
	{
		pCur = pCur->GetNext();
	}

	Node* pNode = nullptr;

	pNode = new Node;

	if (pNode != nullptr)
		pNode->SetData(data);

	pCur->SetNext(pNode);
	return;
}

void Delete(int data)
{
	if (pHeader == nullptr)
	{
		std::cout << "Empty" << std::endl;
		return;
	}

	if (pHeader->GetData() == data)
	{ 
		Node* pDelete = pHeader;
		pHeader = pHeader->GetNext();
		delete pDelete;
		return;
	}

	Node* pCur = pHeader;
	Node* pPre = nullptr;

	while (pCur!= nullptr)
	{
		if (pCur->GetData() == data)
		{
			Node* pDelete = pCur;
			Node* pCurNext = pDelete->GetNext();
			pPre->SetNext(pCurNext);
			delete pDelete;
			return;
		}
		else
		{
			pPre = pCur;
			pCur = pCur->GetNext();
		}
	}
}

void VisitAll()
{
	if (pHeader == nullptr)
	{
		std::cout << "Empty" << std::endl;
		return;
	}

	Node* pCur = pHeader;

	while (pCur != nullptr)
	{
		std::cout << std::to_string(pCur->GetData()) + " ";
		pCur = pCur->GetNext();
	}
}

int main()
{
	while (true)
	{
		std::system("cls");
		int menuindex = 0;
		int newnodedata = 0;
		int deletedata = 0;
		std::cout << "1. PushBack" << std::endl;
		std::cout << "2. Delete" << std::endl;
		std::cout << "3. Visit All" << std::endl;
		std::cout << " Menu Index:";
		std::cin >> menuindex;

		switch (menuindex)
		{
		case 1:
			std::cout << " Node Data:";
			std::cin >> newnodedata;
			PushBack(newnodedata);
			break;
		case 2:
			std::cout << " Delete Data:";
			std::cin >> deletedata;
			Delete(deletedata);
			break;
		case 3:
			VisitAll();
			std::cout << std::endl;
			std::system("pause");
			break;
		default:
			break;
		}
	}

	return 0;
}

🐳실행화면

마치며.. 첫 포스팅이라 쓰는 다시는 없을 후기..

많이 좋아하던 자료구조다. 대학 시절 처음 만난 자료구조고 이 자료구조를 시작으로 프로그래밍에 흥미를 느끼게 됐다. 당시 아는 자료구조가 이거 하나 뿐이라 엄청 지지고 볶았다. 기능들도 추가하고 파일 입출력으로도 구현하고, 이후 다른 자료구조들을 배웠는데도 한 동안 못 놔줬던 기억이 있다. 새로 배웠던 자료구조들이 어려워서 그랬던 거 같기도 하고 하하. 블로그를 시작하게 되면 “링크드 리스트가 첫 포스팅이지 않을까?” 막연히 생각했었는데… 추억에 잠기는 기분이다. 참 좋다!

비트코인과 함께 셀럽이 된 링크드야! 지금처럼 코인 말 잘 듣고 행복하게 잘 살아!

References

위키백과