[C/C++] 연결 리스트 구현

연결 리스트 (Linked List)

• STL(Standard Template Library, 표준 템플릿 라이브러리)의 컨테이너 중 하나로, 각 노드들이 포인터로 연결되어 있는 데이터 구조이다.

• 노드(Node, 마디) : 데이터 하나를 저장하는 단위

• 노드에는 저장하고자 하는 데이터와 다음 노드를 가리키는 주소가 존재한다.

• 데이터를 하나 추가할 때마다 힙 영역에 데이터 하나를 저장할 만큼 메모리 공간을 만든다.

노드는 프로그램이 진행되는 동안 존재해야 되기 때문에 힙 영역에 만들어야 한다.

즉, 동적할당을 사용해야 한다.

• 시작 데이터만 알면 계속해서 다음 데이터를 찾아갈 수 있다.

시간 복잡도(Big-O)

• 최악의 경우 배열의 길이만큼 걸릴 때를 대비하여 시간 복잡도를 확인할 때 빅오 표기법을 사용한다.

1) O(n) : 선형 시간 (n : 데이터 개수)

• 알고리즘의 실행 속도를 n을 기준으로 얼마나 걸리는지 결정된다.

• 알고리즘의 실행 시간이 입력 크기에 정비례한다.

  - 배열에서 검색, 최소/최댓값 찾기 등 연산

  - 연결 리스트에서 순회, 최소 / 최대값 찾기 등 연산

ex) 만약 데이터가 1000개일 때 맨 앞에 데이터를 넣어야 된다면 1000개만큼의 비용과 시간이 도는데, 이는 최악의 경우에 해당한다.

 

2) O(1) : 상수 시간

• 데이터가 아무리 많아도 과정은 바뀌지 않는다.

• 이처럼 n과 무관하게 항상 고정 시간일 때 사용한다.

• O(1)에서 1은 없는 취급한다.

• 입력 데이터 개수에 영향을 받지 않고 절댓값이기 때문에 알고리즘을 수행하는 데 있어서 가장 속도가 빠르다.

가변 배열 vs. 리스트

리스트도 가변 배열처럼 데이터를 계속 추가할 수 있지만, 데이터를 관리하는 방식은 가변 배열과 다르다.
가변 배열은 최종적으로 만들어진 메모리가 연속적인 구조를 가지고 있는 반면, 연결 리스트는 데이터가 띄엄띄엄 띄워져 있다.

1) 가변 배열

• 가변 배열의 시작 주소를 안다.

• 특정 인덱스는 주소 연산으로 접근할 수 있다.

• 데이터 개수의 영향을 받지 않고 데이터가 많아도 시간이 더 오래 걸리지는 않는다.

 

2) 리스트

• 특정 위치로 접근하려면 서로 연결되어 있기 때문에 계속해서 주소 연산을 해야 한다.

• 리스트가 헤드를 알고 있을 때 꼬리에 접근할 때가 최악의 경우이다.

① 데이터가 n개라면 데이터 개수만큼의 접근이 필요하다. = n

헤드에 접근, 역참조, 다음 노드의 주소로 접근하여 다음 노드에 접근하는 등의 작업을 n번 해야 된다는 의미이다.

② 리스트가 꼬리 노드를 포인터로 가리키고 있다고 하면 헤드 노드를 접근할 때가 최악의 경우이다. = n

③ 리스트가 헤드와 꼬리를 동시에 알고 있을 땐 가운데 노드에 접근할 때가 최악의 경우이다. = (1/2)n

• 빅오 표기법에서 계수는 무시하기 때문에 1이든 1/2이든 O(n)으로 본다. (n에 관한 1차식)

 

---

연결 리스트 - C

linkedList.h

#pragma once

// 노드 => 저장하고자 하는 데이터 + 다음 노드의 주소
	// 리스트에 데이터를 넣기 위해서는 노드가 필요하다.
typedef struct _tagNode
{
	int iData;
    //tNode* pNextNode;  // 오류 => 노드를 정의하기도 전에 노드명을 사용했기 때문이다.
	struct _tagNode* pNextNode;  // 본래 이름인 struct _tagNode를 이용하여 선언한다.
} tNode;

// 연결 리스트
typedef struct _tagList
{
	tNode* pHeadNode; // 노드 주소
	int iCount;  // 데이터 개수
	//int iMaxCount;
    // 리스트는 최대치(MaxCount)가 필요없다.
    	// 데이터 추가할 때마다 매번 동적할당을 따로 하기 때문에 Max라는 개념없이 항상 1개로 똑같고, 꽉 찼다는 개념이 없다.
	// 대신에 리스트는 노드들 중에 **첫 번째 노드의 주소값**을 알아야 한다.
} tLinkedList;

// 연결 리스트 초기화 함수
void InitList(tLinkedList* _pList);

// 연결 리스트 데이터 추가
void PushBack(tLinkedList* _pList, int _iData);  // 뒤로 데이터 추가
void PushFront(tLinkedList* _pList, int _iData);  // 앞으로 데이터 추가

// 연결 리스트 메모리 해제
void ReleaseList(tLinkedList* _pList);

 

linkdedList.cpp

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

void InitList(tLinkedList* _pList)
{
	_pList->pHeadNode = nullptr;
	_pList->iCount = 0;
}

void PushBack(tLinkedList* _pList, int _iData)
{
	tNode* pNode = (tNode*)malloc(sizeof(tNode));  // 노드 사이즈만큼 만들고 주소는 노드 단위로 데이터를 사용할 것이므로 tNode*로 받아온다.
	pNode->iData = _iData;
	pNode->pNextNode = nullptr;

	// 지금 들어온 데이터(추가한 데이터)가 처음인지 아닌지를 따져봐야 한다.
	// 만약 현재 들어온 데이터의 개수가 0(또는 pHeadNode(첫 번째 노드)가 nullptr)이라면
	if (0 == _pList->iCount)
	{
		_pList->pHeadNode = pNode;  // 노드의 주소를 저장한다.
	}
	// 노드 안에 데이터가 1개 이상이면 else에 걸린다.
	else
	{
		// 현재 가장 마지막 노드 즉, 바로 앞전의 노드를 찾아서 해당 노드의 pNextNode를 생성시킨 노드의 주소로 채운다.
		// 단방향에서 양방향으로 하려면 Head뿐만 아니라 제일 마지막 노드인 Tail도 알아야 한다.
		tNode* pCurFinalNode = _pList->pHeadNode;
		// ---------- while문 수정 전 ---------- //
		//while (true)
		//{
		//	// pNextNode가 nullptr라면 시작하자마자 현재 기준으로 가장 마지막 노드가 처음 노드이기 때문에 while문을 탈출한다.
		//	if (nullptr == pCurFinalNode->pNextNode)
		//	{
		//		break;  // 보통 한 줄일 때는 괄호를 생략한다.
		//	}

		//	// 헤드 노드의 다음이 있다면, 주소 변수를 본인이 가리키고 있는 pNextNode로 갱신시킨다.
		//	pCurFinalNode = pCurFinalNode->pNextNode;
		//}
		// ↓
        // ---------- while문 수정 후 ---------- //
		// pNextNode가 nullptr이면 0이고, 이는 false를 뜻하므로 반복문이 끝나게 된다.
		// 반대로 0이 아닌 모든 수는 true이기 때문에 pNextNode가 존재한다면 반복문이 실행된다.
		while (pCurFinalNode->pNextNode)
		{
			// 헤드 노드의 다음이 있다면, 주소 변수를 본인이 가리키고 있는 pNextNode로 갱신시킨다.
			pCurFinalNode = pCurFinalNode->pNextNode;
		}

		pCurFinalNode->pNextNode = pNode;  // pNextNode를 지금 생성시킨 노드의 주소로 넣는다.
	}

	++_pList->iCount;  // 데이터 하나가 들어왔으니 카운트 하나 증가한다.
}

// 효율이 좋지 않아서 가변 배열에서는 PushFront()를 구현하지 않았다.
// 각각의 메모리를 옆으로 한 칸씩 복사시키면서 이동시키면 가능은 하다.
// 하지만 데이터의 개수가 많아지면 효율성이 너무 떨어진다.
void PushFront(tLinkedList* _pList, int _iData)
{
	// 새로 생성시킨 노드의 다음을 기존의 헤드로 지정한다.
	tNode* pNewNode = (tNode*)malloc(sizeof(tNode));
	pNewNode->iData = _iData;
	pNewNode->pNextNode = _pList->pHeadNode; // 원래 리스트가 가리키고 있던 헤드가 다음 노드가 되어야 들어올 노드가 그 앞에 들어와서 리스트가 이를 헤드로 지정한다.

	// 리스트의 헤드 노드 포인터를 갱신한다.
	_pList->pHeadNode = pNewNode;

	// 데이터가 들어왔으니 카운트를 증가시킨다.
	++_pList->iCount;
}

// 연결형 리스트 메모리 해제 방법 2가지
// 1. 재귀함수(효율은 좋지 않다.)
// 함수가 데이터의 개수만큼 호출되기 때문에 데이터의 양이 많아지면 효율이 좋지 않기 때문에 구현 방법은 간단하지만 좋은 방법은 아니다.
void Release(tNode* _pNode)
{
	// 탈출 조건
	// 들어온 포인터가 null일 경우에 아무것도 하지 않고 리턴한다.
	if (nullptr == _pNode)
		return;

	//free(_pNode);  // 받자마자 해제하면 데이터가 다 날라가버려서 다음 노드로 갈 수가 없다.
	
	// Release로 먼저 호출하여 먼저 pNextNode의 주소를 받아서 그 다음 노드를 지운다.
	// 그럼 맨 마지막 노드부터 차례대로 지워진다.
	Release(_pNode->pNextNode);
	free(_pNode);  // 그렇게 메모리가 해제되다가 첫 번째 노드까지 돌아오고 나면 free()로 인해 메모리가 해제된다.
}

// 2. 반복문
void ReleaseList(tLinkedList* _pList)
{
	// tLinkedList의 입장에서 알고 있는 것은 pHeadNode뿐이다.
	tNode* pDeleteNode = _pList->pHeadNode;  // 첫 번째 노드를 받아온다.
	// ---------- while문 수정 전 ---------- //
	//while (true)
	//{
	//	tNode* pNext = pDeleteNode->pNextNode;  // 삭제할 노드(pDeleteNode)의 다음 노드(pNextNode)를 pNext에 넣는다.
	//	free(pDeleteNode);  // 해당 메모리 해제
	//	pDeleteNode = pNext;  // 삭제할 노드를 다음 노드로 갱신시킨다.
	//}
	// ↓
    // ---------- while문 수정 후 ---------- //
	// pDeleteNode가 null이 될 때까지 반복문은 반복된다.
	while (pDeleteNode)
	{
		// 다음 노드의 다음 꺼를 기억해두고 지우는 것을 반복한다.
		tNode* pNext = pDeleteNode->pNextNode;  // 삭제할 노드(pDeleteNode)의 다음 노드(pNextNode)를 pNext에 넣는다.
		free(pDeleteNode);  // 해당 메모리 해제
		pDeleteNode = pNext;  // 삭제할 노드를 다음 노드로 갱신시킨다.
	}
}

 

main.cpp

#include <cstdlib>
#include <iostream>
#include "linkedList.h"
#include "Arr.h"

using namespace std;

int main()
{
	// 리스트는 가변 배열처럼 초반에 할당할 필요가 없다.
	// 아직 데이터가 들어오지 않았는데 노드를 미리 만들 필요가 없기 때문이다.
	// 게다가 노드는 데이터가 들어올 때마다 만들어진다.
	tLinkedList list = {};
	InitList(&list);

	// 뒤로 데이터 넣기
	//PushBack(&list, 100);
	//PushBack(&list, 200);
	//PushBack(&list, 300);

	// 앞으로 데이터 넣기
	PushFront(&list, 100);
	PushFront(&list, 200);
	PushFront(&list, 300);

	// 데이터 출력
	tNode* pNode = list.pHeadNode;
	for (int i = 0; i < list.iCount; ++i)
	{
    	cout << pNode->iData << endl;
		pNode = pNode->pNextNode;
	}
    
    // 힙 영역 메모리 해제
	ReleaseList(&list);
    
	return 0;
}

▽ 출력 결과

300
200
100

 

`PushBack()`으로 데이터를 넣은 뒤, 메모리 해제 하기 전 `list` 메모리 상황

---

연결 리스트 - C++

나머지 코드는 수정 사항 없고, `linkedList.cpp`만 수정하면 된다.

`malloc()` → `new`

`free()` → `delete`

linkedList.cpp

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

// 연결 리스트 초기화 함수
void InitList(tLinkedList* _pList) {
    _pList->pHeadNode = nullptr;
    _pList->iCount = 0;
}

// 뒤에 데이터 추가
void PushBack(tLinkedList* _pList, int _iData) {
    tNode* pNode = new tNode;  // new를 사용하여 메모리 할당
    pNode->iData = _iData;
    pNode->pNextNode = nullptr;

    if (_pList->iCount == 0) {
        _pList->pHeadNode = pNode;  // 첫 번째 노드로 설정
    } else {
        tNode* pCurFinalNode = _pList->pHeadNode;
        while (pCurFinalNode->pNextNode) {
            pCurFinalNode = pCurFinalNode->pNextNode;
        }
        pCurFinalNode->pNextNode = pNode;  // 마지막 노드의 pNextNode에 새 노드를 추가
    }

    ++_pList->iCount;
}

// 앞으로 데이터 추가
void PushFront(tLinkedList* _pList, int _iData) {
    tNode* pNewNode = new tNode;  // new를 사용하여 메모리 할당
    pNewNode->iData = _iData;
    pNewNode->pNextNode = _pList->pHeadNode;  // 기존 헤드를 새 노드 뒤에 연결
    _pList->pHeadNode = pNewNode;  // 새 노드를 헤드로 설정
    ++_pList->iCount;
}

// 연결 리스트 메모리 해제 (재귀적으로 메모리 해제)
void Release(tNode* _pNode) {
    if (_pNode == nullptr) return;  // 노드가 nullptr이면 종료

    Release(_pNode->pNextNode);  // 다음 노드부터 메모리 해제
    delete _pNode;  // 현재 노드 메모리 해제
}

// 연결 리스트 메모리 해제 (반복문 사용)
void ReleaseList(tLinkedList* _pList) {
    tNode* pDeleteNode = _pList->pHeadNode;
    while (pDeleteNode) {
        tNode* pNext = pDeleteNode->pNextNode;  // 다음 노드 저장
        delete pDeleteNode;  // 현재 노드 메모리 해제
        pDeleteNode = pNext;  // 다음 노드로 이동
    }
}