연결 리스트 (Linked List)

연결 리스트(Linked List)란?

데이터를 가지고 있는 노드가 다음 노드의 주소를 가지고 있는 리스트이다.

연결 리스트의 특징

메모리만 여유있다면, 크기 제한이 없다.

 

자료의 추가, 삭제가 O(1)에 가능하다.

자료의 탐색이 O(n)으로 느리다.

 

But,

자료를 (추가, 삭제)하기 전에도 탐색을 한번 거쳐야 하기 때문에, (추가, 삭제)가 빠른 것을 장점이라고 말하기 어렵다.

연결 리스트 구현 (그림 설명)

자료를 쉽게 다루기 위해,

Node 클래스 하나를 더미로 만들어 리스트의 시작 노드로 설정한다.

 

1. 데이터 추가

(맨 뒤에 삽입할 때) 받은 데이터로 노드를 하나 생성하고, 노드를 연결해준다.

 

(리스트의 중앙에 삽입할 때) 마찬가지로 노드를 하나 생성하고, 위치를 찾아서 연결해준다.

순서 주의!!

NewNode의 이전 노드에서 먼저 NewNode를 연결해버리면 NewNode의 다음 노드 주소를 잃어버린다.

2. 데이터 삭제

위치를 찾고, 이전 노드와 다음 노드를 연결해준다.

연결을 해주었으면 노드를 삭제한다.

링크드 리스트 구현 (C++)

LinkedList.h

#pragma once
#include <assert.h>

template <typename T>
class LinkedNode
{
	template <typename T>
	friend class LinkedList;

private:
	LinkedNode() :
		mData{},
		mNext{}
	{
	}
	~LinkedNode()
	{

	}
private:
	T mData;
	LinkedNode<T>* mNext;
};

/*
* Size
* IsEmpty
*
* Add_End(data)
* Add_Front(data)
* Remove_End
* Remove_Front
*
* Clear
* FrontValue
* EndValue
* GetValueAt(index)
* InsertAt(index, data)
*/
template <typename T>
class LinkedList
{
public:
	LinkedList() :
		mSize{}
	{
		mBegin = new LinkedNode<T>;
	}
	~LinkedList()
	{
		delete mBegin;
	}
private:
	LinkedNode<T>* mBegin;
	int mSize = 0;

public:
	int Size()
	{
		return mSize;
	}
	bool IsEmpty()
	{
		return mSize == 0;
	}

	void Add_End(T Data)
	{
		LinkedNode<T>* CurrentNode = new LinkedNode<T>();
		CurrentNode->mData = Data;

		LinkedNode<T>* LastNode = mBegin;
		while (LastNode->mNext)
		{
			LastNode = LastNode->mNext;
		}
		LastNode->mNext = CurrentNode;

		mSize++;
	}
	void Add_Front(T Data)
	{
		LinkedNode<T>* CurrentNode = new LinkedNode<T>();
		CurrentNode->mData = Data;

		LinkedNode<T>* NextNode = mBegin->mNext;
		CurrentNode->mNext = NextNode;
		mBegin->mNext = CurrentNode;

		mSize++;
	}

	void Remove_End()
	{
		if (IsEmpty()) return;

		LinkedNode<T>* RemoveNode = mBegin->mNext;
		LinkedNode<T>* LastNode = RemoveNode;
		while (RemoveNode->mNext)
		{
			LastNode = RemoveNode;
			RemoveNode = RemoveNode->mNext;
		}
		delete RemoveNode;
		LastNode->mNext = nullptr;

		mSize--;
	}
	void Remove_Front()
	{
		if (IsEmpty())return;

		LinkedNode<T>* RemoveNode = mBegin->mNext;
		LinkedNode<T>* NextNode = RemoveNode->mNext;

		delete RemoveNode;
		mBegin->mNext = NextNode;

		mSize--;
	}

	void Clear()
	{
		LinkedNode<T>* CurrentNode = mBegin->mNext;
		while (CurrentNode)
		{
			LinkedNode<T>* NextNode = CurrentNode->mNext;
			delete CurrentNode;
			CurrentNode = NextNode;
		}

		mSize = 0;
	}

	T FrontValue()
	{
		assert(!IsEmpty());
		LinkedNode<T>* CurrentNode = mBegin->mNext;
		return CurrentNode->mData;
	}
	T EndValue()
	{
		assert(!IsEmpty());
		LinkedNode<T>* CurrentNode = mBegin->mNext;
		while (CurrentNode->mNext)
		{
			CurrentNode = CurrentNode->mNext;
		}
		return CurrentNode->mData;
	}
	T GetValueAt(int Index)
	{
		assert(Index < mSize);
		int mIndex = 0;
		LinkedNode<T>* CurrentNode = mBegin->mNext;
		while (mIndex < Index)
		{
			CurrentNode = CurrentNode->mNext;
			mIndex++;
		}
		return CurrentNode->mData;
	}
	void InsertAt(int index, T data)
	{
		assert(mSize >= index);

		LinkedNode<T>* NewNode = new LinkedNode<T>();
		NewNode->mData = data;

		LinkedNode<T>* PrevNode = mBegin->mNext;
		int nodeIndex = index;
		while (nodeIndex > 1)
		{
			PrevNode = PrevNode->mNext;
			nodeIndex--;
		}
		LinkedNode<T>* NextNode = PrevNode->mNext;
		PrevNode->mNext = NewNode;
		NewNode->mNext = NextNode;

		mSize++;
	}
};

리스트 사용법

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

void PrintList(LinkedList<int>& list)
{
	for (int i = 0; i < list.Size(); i++)
	{
		std::cout << list.GetValueAt(i) << " ";
	}
	std::cout << std::endl;
}

int main()
{
	LinkedList<int> ListInt{};

	ListInt.Add_End(0);
	ListInt.Add_End(1);
	ListInt.Add_End(2);
	ListInt.Add_Front(4);
	ListInt.Add_Front(5);
	ListInt.Add_Front(6);
	PrintList(ListInt);	// 6 5 4 0 1 2

	ListInt.Remove_End();
	ListInt.Remove_Front();
	PrintList(ListInt);	// 5 4 0 1

	std::cout << ListInt.EndValue() << std::endl;	// 1
	std::cout << ListInt.FrontValue() << std::endl;	// 5

	ListInt.InsertAt(2, 3);
	PrintList(ListInt);	// 5 4 3 0 1

	ListInt.Clear();
	PrintList(ListInt);	// 출력 없음
}

 

리스트를 사용할 때, 주의할 점이 있다.

아래 코드와 같이 GetValueAt을 이용하여 리스트 전체를 출력하려고 할 때, 문제가 생긴다.

 

나는 테스트용으로 그냥 작성했지만, 실제로는 쓰지 말자. 무식한 방법이다.

GetValueAt 함수 안에서 While 문이 돌기 때문에, 실제로는 이중 반복문이 돌아가고 있는 것이다.

 

List에서 시작 포인터를 받아온 뒤, 사용하는 곳에서 반복문을 돌리며 출력하는 것이 좋은 방법이다.

void PrintList(LinkedList<int>& list)
{
	for (int i = 0; i < list.Size(); i++)
	{
		std::cout << list.GetValueAt(i) << " ";
	}
	std::cout << std::endl;
}