[자료구조] 링크드 리스트(Singly Linked List) (C++)

1. 개념

각 요소를 노드(Node)라고 부르며, 링크드 리스트는 '노드를 연결해서 만드는 리스트'라고 해서 붙여진 이름이다.

링크드 리스트의 노드는 데이터를 보관하는 필드와 다음 노드 주소를 가리키는 포인터로 이루어져 있다.

 

데이터가 늘어날 때마다 노드를 만들어서 테일에 붙이면 된다. 리스트 사이에 새로운 노드를 끼워 넣거나 제거하는 것도 간편하다.

 

 

template<typename T>
struct Node
{
	T data;			// 데이터
	Node<T>* nextNode;	// 다음 노드를 가리키는 포인터

	Node<T>(T value) : data(value), nextNode(NULL) {}
};

template<typename T>
class LinkedList
{
	Node<T>* head;
	Node<T>* tail;
	int size = 0;

public:
	LinkedList() : head(NULL), tail(NULL) {}
	~LinkedList()
	{
		Node<T>* deleteNode;
		while (head->nextNode != NULL)
		{
			deleteNode = head;
			head = head->nextNode;
			delete deleteNode;
		}
	}
    //...
};C++

기존에 공부할 때는 항상 int형으로만 구현했었다. 이번에는 어떠한 타입이든 담을 수 있도록 template을 사용해 본다.

이 Node를 기반으로 동작하는 LinkedList 클래스 또한 template를 사용하며, LinkedList 클래스 내부에서 구현해야 할 기능은 다음과 같다.

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

 

 

2. 노드 추가

void addNode(T data)
{
	Node<T>* newNode = new Node<T>(data);
	++size;

	// head가 NULL이라면 현재 Linked List는 비어 있는 상태
	// 추가한 노드를 head와 tail이 가리키게 하고 return 처리
	if (head == NULL)
	{
		head = tail = newNode;
		return;
	}

	tail->nextNode = newNode;
	tail = newNode;
}C++

 

 

3. 노드 탐색

void showList() const
{
	Node<T>* findNode = head;

	while (findNode != NULL)
	{
		cout << findNode->data << " ";
		findNode = findNode->nextNode;
	}
	cout << endl;
}C++

Node<T>* findNode(int location) const
{
	Node<T>* searchNode = head;
	int index = location;

	while(searchNode != NULL && --index >= 0)
	{
		searchNode = searchNode->nextNode;
	}
	
	return searchNode;
}

T findNodeData(int location) const
{
	Node<T>* searchNode = head;
	int index = location;

	while (searchNode != NULL && --index >= 0)
	{
		searchNode = searchNode->nextNode;
	}

	return searchNode->data;
}
C++

 

 

4. 노드 삭제

void removeNode(T data)
{
	// 탐색용 포인터, 삭제할 Node의 이전 Node를 저장함
	Node<T>* findNode = head;
	// 삭제될 Node를 임시로 저장할 포인터
	Node<T>* deleteNode;

	while (findNode != NULL)
	{
		if (findNode->nextNode != NULL && findNode->nextNode->data == data)
			break;
		findNode = findNode->nextNode;
	}

	// nullptr이면 해당 데이터를 찾지 못함
	if (findNode != NULL)
	{
		deleteNode = findNode->nextNode;
		findNode->nextNode = deleteNode->nextNode;
		--size;
		
		delete deleteNode;
	}
}
C++

 

 

5. 노드 삽입

void insertNode(T data, int index)
{
	// index가 SLL 사이즈보다 크거나 음수인 경우 예외 처리
	if (index > size || index < 0)
	{
		cout << "invalid index : " << index << endl;
		return;
	}

	Node<T>* newNode = new Node<T>(data);

	// head에 추가
	if (index == 0)
	{
		// 만약 비어 있다면
		if (head == NULL)
			tail = newNode;

		newNode->nextNode = head;
		head = newNode;
	}
	// tail에 추가
	else if (index == size)
	{
		// 만약 비어 있다면
		if (head == NULL)
			head = tail = newNode;
		else
		{
			tail->nextNode = newNode;
			tail = newNode;
		}
	}
	else
	{
		Node<T>* findNode = head;
		Node<T>* nextNode = findNode->nextNode;


		for (int i = 1; i < index; ++i)
		{
			findNode = nextNode;
			nextNode = findNode->nextNode;
		}

		newNode->nextNode = nextNode;
		findNode->nextNode = newNode;
	}

	++size;
}
C++

 

 

6. 노드 출력

void showList() const
{
	Node<T>* findNode = head;

	cout << "size of SLL: " << size << endl;

	while (findNode != NULL)
	{
		cout << findNode->data << " ";
		findNode = findNode->nextNode;
	}
	cout << endl;
}
C++

 

 

장점/단점

장점

• 새로운 노트의 추가/삽입/삭제가 쉽고 빠르다.

단점

• 다음 번 노드를 가리키는 포인터 멤버 변수가 존재하기 때문에, 각 노드마다 4byte의 메모리가 추가로 필요하다.
• 노드 탐색의 비용이 크며, 속도도 매우 느리다. 노드의 개수가 n개라면, 최악의 경우 n회의 노드 탐색을 통해 찾아낼 수 있다.

 

노드의 추가/삽입/삭제는 빠르지만 특정 위치에 있는 노드를 찾는 연산은 느리다!