[자료구조]#1_연결 리스트(Linked List)

 

[자료구조]#1_연결 리스트(Linked List)

 

선형 자료 구조 중 "연결 리스트"에 대해 알아보겠습니다.

 

---

 

Overview

 

1. 연결 리스트?
2. 삽입, 제거 알고리즘
3. 탐색 알고리즘

 

연결 리스트

1. 개념

• 연결 리스트는 노드 기반의 선형 자료구조로, 각 노드는 데이터 필드와 다음 노드를 가리키는 포인터로 구성되어 있습니다. 각 항목/노드의 논리적 저장 순서는 물리 저장 순서와 일치하지 않습니다.

 

2. 특징

 

 

1. 각 항목은 "데이터 필드" + "포인터"를 갖는 노드 형식으로, 다음 노드를 가리키는 "포인터"를 갖습니다.
2. 접근 방법은 첫 노드부터 포인터를 타고 순차적으로 접근하며, O(n)의 수행 속도를 가집니다.
3. 삽입, 삭제 방법은 "포인터" 연결을 끊고, 연결하는 방식으로 매우 간단합니다.
4. 크기는 고정되어 있지 않습니다, 즉 추가적인 메모리 공간을 동적 할당 받을 수 있습니다.

 

삽입, 삭제

1. 삽입

#include <iostream>
#include <string>
using namespace std;

typedef struct _Node {
	int Data;
	string Name;
	struct _Node* Next;
}Node;

int main()
{
	Node* Head = nullptr;
	Node* New = new Node();

	// 1. 최초의 노드 삽입
	New->Data = 1;
	New->Name = "First";
	New->Next = nullptr;

	if (Head == nullptr)
	{
		Head = New;
	}

	cout << "최초의 삽입 : ";
	cout << Head->Name << endl;

	// 2. 맨 앞으로 노드 삽입
	Node* New2 = new Node();
	New2->Data = 2;
	New2->Name = "Second";
	New2->Next = nullptr;
	if (Head != nullptr)
	{
		New2->Next = Head;
		Head = New2;
	}

	cout << "연결 리스트 맨 앞으로 삽입 : ";
	cout << Head->Name << endl;

	// 3. Second Node -- First Node 중간에 삽입
	Node* New3 = new Node();
	New3->Data = 3;
	New3->Name = "Third";
	New3->Next = nullptr;
	
	New3->Next = New2->Next;
	New2->Next = New3;
	
	cout << "연결 리스트 중간으로 삽입 : ";
	Node* CurrentNode = Head;
	while (CurrentNode != nullptr)
	{
		cout << CurrentNode->Name << ' ';
		CurrentNode = CurrentNode->Next;
	}

}

 

결과 화면

 

Details

 

 

1. "Head"는 단순히 연결 리스트의 시작점을 가리킵니다.
2. 연결 리스트의 삽입 알고리즘의 원리는 매우 간단합니다.
3. C가 새롭게 들어갈 위치를 기준으로 다음 노드는 C의 Next 노드가 됩니다.
4. C가 새롭게 들어갈 위치를 기준으로 이전 노드의 Next 노드는 C가 됩니다.

 

2. 삭제

#include <iostream>
#include <string>
using namespace std;

typedef struct _Node {
	int Data;
	string Name;
	struct _Node* Next;
}Node;

int main()
{
	Node* Head = nullptr;
	Node* New = new Node();

	New->Data = 1;
	New->Name = "First";
	New->Next = nullptr;

	if (Head == nullptr)
	{
		Head = New;
	}

	Node* New2 = new Node();
	New2->Data = 2;
	New2->Name = "Second";
	New2->Next = nullptr;

	New->Next = New2;

	Node* New3 = new Node();
	New3->Data = 3;
	New3->Name = "Third";
	New3->Next = nullptr;

	New2->Next = New3;

    // 0. 연결 리스트 구현
	Node* Curr = Head;
	while (Curr != nullptr)
	{
		cout << Curr->Name << ' ';
		Curr = Curr->Next;
	}

	cout << '\n';

	// 1. 노드 삭제
	Curr = Head;
	while (Curr != nullptr)
	{
		if (Curr->Next->Next == nullptr)
			Curr->Next = nullptr;

		Curr = Curr->Next;
	}

	cout << "노드 삭제 : ";
	Curr = Head;
	while (Curr != nullptr)
	{
		cout << Curr->Name << ' ';
		Curr = Curr->Next;
	}

}

 

결과 화면

 

 

Details

 

 

1. 연결 리스트의 삭제 알고리즘은 "Next"를 끊어주는 것만으로 간단하게 작성할 수 있습니다.
2. 먼저, 삭제할 노드는 "Next(다음 노드를 가리키는 포인터)"를 이전 노드에게 넘겨줍니다. 
3. 그리고, 삭제할 노드는 "Next"를 nullptr로 변경함으로서 연결 리스트에서 제외됩니다.
4. 배열과 달리, 탐색 작업이 비교적 느린 반면에, 삽입 + 삭제 성능이 비교적 높습니다.

 

탐색

1. 탐색

Node* Curr = Head;
while (Curr != nullptr)
{
	cout << Curr->Name << ' ';
	Curr = Curr->Next;
}

 

Details

 

1. 연결 리스트의 탐색은 "Head"부터 순차적으로 수행됩니다.
2. Index를 통해 빠르게 항목에 접근할 수 있는 배열과 달리, 연결 리스트의 탐색은 O(n)의 시간 복잡도를 갖습니다.
3. Head 부터 시작해, 각 노드가 갖고 있는 다음 노드를 가리키는 포인터를 통해서 순차적으로 탐색을 진행합니다.

 

Summary

 

1. 연결 리스트는 순서를 갖는 데이터 목록입니다.
2. 논리적 저장 순서와 물리적 저장 순서가 일치하지 않습니다. 
3. 연결 리스트의 각 노드는 "데이터 영역" + "다음 노드를 가리키는 포인터"를 갖습니다.
4. 삽입, 삭제 알고리즘은 비교적 간단하며, 빠릅니다.
5. 탐색 알고리즘은 순차적으로 진행되며, 배열과 비교했을 때 비교적 느린 편입니다.
6. 연결 리스트의 크기는 고정되어 있지 않으며, 필요시 동적으로 할당받습니다.