[자료구조] 싱글 링크드 리스트(Single Linked List)

싱글 링크드 리스트(Single Linked List)

 

싱글 링크드 리스트란?

• 노드를 연결해서 만든 리스트다.
• 데이터와 포인터를 이용하여 노드를 만들고 이것을 기차처럼 연결시켜준다.
• 머리(헤드)와 꼬리(테일)을 가지고있다.
• 데이터의 추가, 삽입, 삭제는 용이하나(가르키는 노드만 바꿔주면 됨) 그 과정까지 탐색 속도가 떨어진다.

데이터와 다음 노드에 대한 포인터로 이루어져있다.

헤드와 테일이 있으며 노드끼리 연결 되어 있다.

싱글 링크드 리스트 구현

• 노드 추가
• 노드 탐색
• 노드 삭제
• 노드 삽입

싱글 링크드 리스트 클래스

class Node
{
public:
	Node();
private:
	int Data;
	Node* Next;
	friend class LinkedList;

public:

	int GetData()
	{
		return Data;
	}
};

class LinkedList
{
public:
	LinkedList();
private:
	Node* Head;
	Node* Tail;

public:

	void Add(const int& NewData);
	bool Search(const int& Data);
	void Insert(const int& NewData, const int& Index);
	void Remove(const int& Data);

	Node* GetNodeAt(const int& Index);
	void Show();
};

노드 추가

새로운 노드를 추가하는 그림

11의 데이터를 가진 노드의 Next는 테일을 가리키는데 이걸 지우고 새로운 노드를 가르키게 해준뒤 새로운 노드는 테일을 가르키게 만든다

먼저 테일전까지의 노드에 접근하기 위해선 선형으로 연결되어있는 노드들을 통해 접근을 해야한다.

테일전까지 접근을 하고 기존노드를 지운 후 새로운 노드와 연결을 시켜주고 새로운 노드는 테일에 연결 시켜준다.

void LinkedList::Add(const int& NewData)
{
	Node* NewNode = new Node();

	if (NewNode != nullptr)
	{
		NewNode->Data = NewData;
	}

	if (Head->Next != nullptr)
	{
		Node* CurrentNode = Head;

		if (CurrentNode != nullptr)
		{
			while (CurrentNode->Next != Tail)
			{
				CurrentNode = CurrentNode->Next;
			}

			CurrentNode->Next = NewNode;
			NewNode->Next = Tail;
		}
	}
	else
	{
		Head->Next = NewNode;
		NewNode->Next = Tail;
	}
}

 

노드 탐색

테일 전까지의 노드를 순회하면서 같은 데이터를 찾아야한다.

bool LinkedList::Search(const int& Data)
{
	Node* CurrentNode = Head;

	if (CurrentNode != nullptr)
	{
		while (CurrentNode->Next != Tail)
		{
			if (CurrentNode->Next->Data == Data)
			{
				return true;
			}

			CurrentNode = CurrentNode->Next;
		}
		std::cout << "검색 할 노드가 없습니다" << std::endl;
		return false;
	}
	else
	{
		std::cout << "헤드가 없습니다" << std::endl;
		return false;
	}
}

노드 삽입

데이터5와 데이터11사이에 삽입을 해준다.

첫번째 노드와 두번째 노드의 사이에 새로운 노드를 사입하는 과정

헤드의 다음노드를 첫번째 노드라고 생각하고 첫 번째 노드와 두 번째 노드사이에 새로운 노드를 넣는다.

그림에선 첫 번째 뒤에 삽입 하기 위해 1이라는 인덱스를 필요로 한다.

void LinkedList::Insert(const int& NewData, const int& Index)
{
	Node* CurrentNode = Head;

	if (CurrentNode != nullptr)
	{
		for (int i = 0; i < Index; ++i)
		{	
			if (CurrentNode != nullptr)
			{
				CurrentNode = CurrentNode->Next;
			}
			else
			{
				std::cout << Index << "번째의 노드가 없습니다" << std::endl;
				return;
			}
		}
	}

	if (CurrentNode == nullptr)
	{
		std::cout << Index << "번째의 노드가 없습니다" << std::endl;
		return;
	}

	Node* NewNode = new Node();
	if (NewNode != nullptr)
	{
		NewNode->Data = NewData;
		NewNode->Next = CurrentNode->Next;
		CurrentNode->Next = NewNode;
	}
}

노드 제거

20과 6사이에 있는 노드를 지우는 그림이다.

테일 전까지 노드를 순회하면서 같은 데이터를 찾고 그 데이터가 있으면 제거를 할 수 있다.

여기서 중요한 점은 다음 노드를 연결할때 순서가 중요한다.

제거 하기전에 제거 해야하는 노드의 전 노드를 찾고 그림에선 데이터 20의 노드 이다.

데이터 20의 노드를 제거 해야하는 노드의 다음 노드를 연결 시켜주고 노드를 제거해야 한다.

제거해야할 노드를 먼저 제거하면 제거하는 다음 노드를 알 수 없기 때문이다.

void LinkedList::Remove(const int& Data)
{
	Node* CurrentNode = Head;

	if (CurrentNode != nullptr)
	{
		while (CurrentNode->Next != Tail)
		{
			if (CurrentNode->Next->GetData() == Data)
			{
				Node* RemoveNode = CurrentNode->Next;
				CurrentNode->Next = CurrentNode->Next->Next;
				std::cout << RemoveNode->GetData() << std::endl;
				delete RemoveNode;
				return;
			}
			CurrentNode = CurrentNode->Next;
		}
		std::cout << Data << "가 리스트에 존재하지 않습니다" << std::endl;
	}
}

메인 코드

int main()
{
	LinkedList* List = new LinkedList();

	if (List != nullptr)
	{
		List->Add(5);
		List->Add(8);
		List->Add(1);
		List->Insert(10, 2);
		List->Search(11);
		List->Remove(8);
		List->Remove(55);
		List->Show();
	}
}

Add함수를 통해 5, 8, 1 을 추가해주고

Insert함수를 통해 10의 데이터를 2번째에 삽입시켜주면 5, 8, 10, 1이 저장되며

Search함수로 검색을 하면 없는 데이터이기에 검색에 실패하고

Remove함수를 8을 제거 해서 5, 10, 1 이 되고 55를 제거할려 하지만 없기때문애 실패한다.