728x90

■ 연결 리스트(Linked List)

배열은 메모리에 연속적으로 저장되며 크기가 고정되는 “정적 메모리 구조”이기 때문에, 한번 생성된 후에는 길이를 직접 변경할 수 없다.

  • 정확히 말하면 길이를 늘일 수 없는 것이 아닌, 더 큰 배열을 새로 생성한 뒤 기존 데이터를 모두 복사해야 하므로 비효율적이다.

[링크드 리스트]

그래서 필요할 때마다 데이터를 저장할 수 있는 “노드(연결이 가능한 객체)”를 동적 할당하여 이들을 연결한 것이 바로 연결 리스트이다.

  • 즉, 처음 데이터는 그 다음그다음 데이터가 저장된 위치를 가리키고, 다음 데이터는 그다음 데이터의 위치를 가리킨다.

연결하는 방식에 따라서 연결 리스트도 여려 종류가 존재한다. 하나씩 천천히 살펴보도록 하자.

 

■ 단일 연결 리스트(Singly Linked List)

단일 연결 리스트는 위 그림처럼 각 노드가 오직 다음 노드를 가리키는 포인터 하나만을 가지는 연결 리스트 구조이다.

 

여기서 중요한 점은, “데이터를 어디에 저장해야 하는가?”이다. 배열과 달리 연결 리스트는 메모리상 연속적인 구조가 아니며, 저장 위치가 고정되지 않기 때문에 삽입되는 데이터를 어떤 노드와 연결할지가 핵심이다.

🛠️새로운 데이터를 맨 앞에 삽입

[새로운 데이터를 맨 앞에 삽입하는 경우]

새로운 데이터를 맨 앞에 저장하는 경우는 아래의 과정을 거친다.

  1. 새로운 노드가 기존 Head노드(첫 데이터를 가리키는 노드)가 가리키던 노드를 가리키게 한다.
  2. Head노드가 추가된 노드를 가리키도록 변경한다.

이 경우 맨 마지막 노드를 가리키는 별도의 노드(Tail노드)가 필요하진 않지만, 저장 순서를 유지하지 않는다는 단점이 있다.

 

🛠️새로운 데이터를 맨 뒤에 삽입

[새로운 데이터를 맨 뒤에 삽입하는 경우]

새로운 데이터를 맨 뒤에 저장하기 위해서 맨 끝을 가리키고 있는 Tail노드가 필요하다.

  1. Tail노드가 가리키는 노드가 새 노드를 가리키게 만든다.
  2. Tail노드가 새로운 노드를 가리키게 만든다.

이 경우 저장 순서를 그대로 유지하지만, 데이터를 추가할 때마다 Tail 노드를 갱신해야 한다는 단점이 있다.

  • 이 부분에선 머리에 노드를 저장하는 방식을 사용하여 구현하겠다.

 

1. LinkedList.h

 

정의 기능
void InitList(List* pList) 초기화 할 리스트의 주소 값을 전달. 리스트 생성 후 가장 먼저 호출.
void Add(List* pList, LData data): 리스트에 데이터를 저장.
bool First(List* pList, LData* data) 리스트의 첫 번째 데이터를 data가 가리키는 메모리에 저장.
     →참조 여부에 따라 bool 값 반환.
bool Next(List* pList, LData* data) 참조된 데이터의 다음 데이터가 data가 가리키는 메모리에 저장.
     →참조 여부에 따라 bool 값 반환.
LData Remove(List* pList) First, Next의 마지막 반환 데이터를 삭제 후 반환.
LData RemoveAt(List* p_list, int index); 특정 index위치에 저장된 값 삭제
int Count(List* pList) 리스트에 저장된 데이터 수 반환.

[LinkedList.h]

링크드 리스트의 추상 자료형 역시 앞서 구현한 배열 기반 리스트와 거의 동일하다.

 

추가된 점은 현재 참조하고 있는 데이터를 삭제하는 Remove()함수와 다르게 추가로 특정 인덱스에 저장된 값을 삭제하는 RemoveAt() 함수를 추가로 구현하였다.

 

head와 cur 같은 포인터 변수를 전역변수로 생성하지 않고 하나로 묶어 별도의 구조체를 정의했다.

  • 필요에 따라 다수의 리스트 자료구조가 필요할 수 있기 때문이다.

 

2. LinkedList.cpp

2-1. 리스트 초기화 함수(InitList)

void InitList(List* p_list)
{
	if (p_list == nullptr) return;

	// head가 존재하지 않는다면
	if(p_list->head == nullptr)
	{
		p_list->head = new Node;
		return;
	}

	// head에 다음 데이터가 존재한다면
	if(p_list->head->nextNode != nullptr)
	{
		auto cur = p_list->head->nextNode;
		while(cur != nullptr)
		{
			auto next = cur->nextNode;
			delete cur;
			cur = next;
		}

		p_list->head->nextNode = nullptr;
		p_list->cur = nullptr;
		p_list->count = 0;
	}
}

리스트에 데이터가 존재하지 않으면, 첫 노드를 가리키는 head노드를 할당한다.

단, 데이터가 존재하는 상태에서 InitList()함수를 호출하면, 기존 할당된 데이터를 삭제할 수 있도록 구현하였다.

[연결된 노드 삭제]

연결 리스트는 각 노드에 저장된 “다음 노드를 가리키는 포인터”를 통해 순차적으로 탐색을 진행한다.

 

따라서 삭제하려는 노드가 어떤 노드를 가리키고 있었는지(다음 노드의 포인터)를 저장하지 않은 상태에서 곧바로 삭제하면, 그 뒤에 연결되어 있던 노드들의 정보에 접근할 수 없다.

[리스트에 저장된 모든 데이터 삭제 과정 - 1]

Head노드가 가리키는 첫 노드부터 삭제를 진행한다. 이때, 삭제 대상 노드에 저장된 다음 노드를 가리키는 포인터를 먼저 저장한 후 delete를 수행한다.

[리스트에 저장된 모든 데이터 삭제 과정 - 2]

노드를 삭제한 후에는 cur포인터를 미리 저장해둔 다음 노드로 이동시킨다. 즉, cur = next; 로 갱신한 뒤, cur 포인터가 nullptr이 될 때까지 위의 과정을 반복한다.

 

2-2. 리스트 삽입 함수(Add) 

void Add(List* p_list, LData data)
{
	auto node = new Node;
	node->data = data;

	auto firstNode = p_list->head->nextNode;
	node->nextNode = firstNode;
	p_list->head->nextNode = node;

	p_list->count++;
}

[리스트에 데이터 추가]

새로운 데이터를 리스트의 맨 앞에 삽입하는 과정은 다음과 같다.

  1. 먼저 현재 리스트의 첫 번째 노드를 임시 포인터에 저장한다.
    • 즉, head→nextNode가 가리키는 노드를 기억해 둔다.
  2. 새로 생성한 노드를 Head가 가리키도록 설정한다.
    • head→nextNode = node;
  3. 새 노드의 next 포인터가 기존 첫 번째 노드를 가리키도록 연결한다.
    • node → nextNode = firstNode;

이 과정을 통해, 새로운 노드는 리스트의 첫 번째 노드가 되고, 기존 노드들은 그 뒤에 그대로 연결된다.

 

2-3. 리스트 조회 함수(First, Next) 

bool First(List* p_list, LData* data)
{
	if(CheckListEmpty(p_list) == true)
	{
		cout << "저장된 데이터가 없습니다!" << endl;
		return false;
	}

	p_list->cur = p_list->head->nextNode;
	p_list->prev = p_list->head;

	*data = p_list->cur->data;

	return true;
}

bool Next(List* p_list, LData* data)
{
	if (CheckListEmpty(p_list) == true)
	{
		return false;
	}

	if(p_list->cur->nextNode == nullptr)
	{
		return false;
	}	

	p_list->prev = p_list->cur;
	p_list->cur = p_list->cur->nextNode;

	*data = p_list->cur->data;
	return true;
}

bool CheckListEmpty(List* p_list)
{
	return p_list == nullptr || p_list->head == nullptr 
		|| p_list->head->nextNode == nullptr;
}

First함수는 리스트 탐색을 시작하기 위한 초기화 함수이다.

이 함수를 호출하면 탐색 위치가 리스트의 첫 번째 노드로 이동하며, 이후의 데이터는 Next 함수를 통해 순차적으로 조회할 수 있다.

  • cur 포인터는 현재 노드를 가리키며, First() 함수에서 첫 번째 노드를 가리키도록 설정된다.
  • prev 포인터는 이전에 탐색한 노드를 가리키며, 초기 상태에서는 Head를 가리키도록 설정한다.

이렇게 구현함으로써, Next함수가 호출될 때 cur노드는 다음 노드로 이동하고, prev는 cur의 이전 노드를 추적할 수 있다.

 

2-4. 리스트 삭제 함수(Remove, RemoveAt) 

LData Remove(List* p_list)
{
	if(p_list->count == 0)
	{
		cout << "삭제할 데이터가 없습니다." << endl;
		return;
	}

	auto deleteNode = p_list->cur;
	auto value = deleteNode->data;

	p_list->prev->nextNode = deleteNode->nextNode;
	p_list->cur = p_list->prev;

	delete deleteNode;
	p_list->count--;

	return value;
}

LData RemoveAt(List* p_list, int index)
{
	if(CheckListEmpty(p_list) == true || index > p_list->count - 1 
		|| index < 0)
	{
		cout << "Out of Range!" << endl;
		return LData();
	}

	LData data;

	First(p_list, &data);
	for(int i = 0; i != index; ++i)
	{
		Next(p_list, &data);
	}

	return Remove(p_list);
}

InitList() 함수는 데이터가 존재할 시 모든 노드를 삭제하기 때문에 이전 노드와 다음 노드를 연결할 필요가 없다.

 

하지만 특정 노드 하나만 삭제하는 경우에는, 삭제되는 노드의 앞 노드(prev)와 뒤 노드(cur→nextNode)를 서로 연결하는 과정이 필요하다.

[노드의 삭제 과정]

노드를 삭제할 때는 다음 순서로 진행한다.

  1. 현재 노드(cur)의 next 포인터를 이전 노드(prev)의 next에 연결한다.
    • 즉, p_list->prev->nextNode = deleteNode->nextNode;를 수행하여 삭제할 노드를 리스트에서 분리한다.
  2. cur포인터를 prev위치로 되돌린다.
  3. 삭제할 노드를 메모리에서 해제한다.

RemoveAt 함수도 동일하게 원하는 위치까지 cur포인터를 이동시킨 후 노드 삭제 함수를 호출한다.

단방향 연결 리스트의 단점은 구현 방식에서도 드러난다. 노드를 삭제하기 위해서는 이전 노드(prev)를 알아야 하는데, 단방향 리스트는 다음 노드(next)의 정보만 저장하고 있기 때문에 이전 노드를 찾기 위해 매번 처음부터 탐색해야 한다.

 

또한 단방향 리스트는 시작 노드에서 끝 노드 방향으로만 탐색이 가능하며, 역방향 탐색은 불가능하다.

이러한 제약을 해결하기 위해 다음에는 양방향 연결 리스트(Doubly Linked List)를 구현해 보겠다.

 

■ 링크드 리스트 응용 - 정렬 기능 구현

기존 Add() 함수를 수정하여, 리스트에 새로운 데이터가 삽입될 때 자동으로 오름차순 정렬되도록 만들어보자.

#pragma once
typedef int LData;

struct LinkedList
{
	Node* head = nullptr;
	Node* cur = nullptr;
	Node* prev = nullptr;
	// 함수 포인터
	int (*comp)(LData d1, LData d2) = nullptr;
	int count = 0;
};

// 정렬 기준을 등록하는 함수
void SetSortedRule(List* p_list, int (*comp)(LData d1, LData d2));

[LinkedList.h]

void Add(List* p_list, LData data)
{
	auto node = new Node;
	node->data = data;

	if(p_list->comp != nullptr)
	{
		auto cur = p_list->head;

		while(cur->nextNode != nullptr &&
			p_list->comp(data, cur->nextNode->data) != 0)
		{
			cur = cur->nextNode;
		}

		node->nextNode = cur->nextNode;
		cur->nextNode = node;
	}
	else
	{
		auto firstNode = p_list->head->nextNode;
		node->nextNode = firstNode;
		p_list->head->nextNode = node;
	}

	p_list->count++;
}

void SetSortedRule(List* p_list, int(*comp)(LData d1, LData d2))
{
	p_list->comp = comp;
}

// 조건함수(Main.cpp에 작성)
int SortedRule(LData d1, LData d2)
{
	if (d1 < d2)
		return 0;
	if(d1 >= d2)
		return 1;
}

[LinkedList.cpp]

LinkedList 구조체에 정렬 기준을 결정하는 함수 포인터(comp)가 추가되었다.

 

이 포인터에 정렬 기준 함수를 등록(SetSortedRule) 하면, Add() 호출 시 해당 기준에 따라 적절한 위치에 노드가 삽입된다.

[노드 정렬 추가]

cur 포인터는 항상 삽입 위치 바로 앞 노드를 가리킨다.

  • cur→nextNode가 nullptr이 아니고, 추가할 데이터가 다음 노드의 데이터보다 클 경우 cur을 다음 노드로 이동시킨다.

조건에 맞는 위치를 찾으면, cur→nextNode에 새 노드를 연결하고, 새 노드의 nextNode가 기존의 cur→nextNode를 가리키게 만들어 연결 순서를 유지한 채 삽입을 완료한다.

728x90

'C++ > 자료구조' 카테고리의 다른 글

[C++, 자료구조] stack의 응용 : 계산기 프로그램  (0) 2025.11.11
[C++, 자료구조] 스택(Stack)  (1) 2025.11.11
[C++, 자료구조] 양방향 연결 리스트(Doubly Linked List)  (0) 2025.10.23
[C++, 자료구조] 순차 리스트(ArrayList)와 추상 자료형  (0) 2025.10.23

티스토리툴바