[DATA STRUCTURE] 03. 단방향 연결 리스트(Singly Linked List)

아래의 코드는 C++로 구현된 단방향 연결 리스트다.

구현된 기능은 노드 추가와 노드 삭제 그리고 노드를 역방향으로 뒤집는 기능이며 헤더 파일에 인라인 형태로 작성했다.

 

 

#pragma once
#include <iostream>

template <typename T>
struct Node {

	T data;
	Node<T>* next;
};

template <class T>
class fwd_list {
private :

	Node<T>* nodeHead;
	int nSize;

public :

	fwd_list() {
		
		nodeHead = nullptr;
		nSize = 0;
	}

	~fwd_list() {

		while (!isEmpty()) {

			pop();
		}
	}

	void push(const T& data) {

		Node<T>* newNode = new Node<T>{ data, nullptr };
		
		if (nodeHead == nullptr) { //헤드 노드가 비어있다면 newNode를 삽입

			nodeHead = newNode;
		
		} else { //헤드 노드가 비어있지 않다면 

			newNode->next = nodeHead;
			nodeHead = newNode;
		}
		nSize++;
	}

	void pop() {
		
		if (nodeHead == nullptr) { //리스트가 비어있다면 동작X

			return;
		}

		Node<T>* nodeCurr = nodeHead;
		Node<T>* nodeRear = nullptr; 

		while (nodeCurr->next != nullptr) {

			nodeRear = nodeCurr;
			nodeCurr = nodeCurr->next;
		}

		delete nodeCurr; //마지막 노드 삭제

		nodeRear->next = nullptr; //이전 노드의 끝을 nullptr로 설정
		nSize--;
	}

	void smart_pop(const T& data) {

		if (nodeHead == nullptr) { //리스트가 비어있다면 동작X

			return;
		}

		Node<T>* nodeCurr = nodeHead;
		Node<T>* nodeRear = nullptr;

		while (nodeCurr->next != nullptr) {

			if (nodeCurr->data == data) {

				if (nodeRear == nullptr) {

					nodeHead = nodeCurr->next;
				
				} else {
				
					nodeRear->next = nodeCurr->next; //이전 노드의 끝을 다음 노드로 이어붙임
				}

				delete nodeCurr; //현재 노드 삭제

				nSize--;
				return;
			}

			nodeRear = nodeCurr;
			nodeCurr = nodeCurr->next;
		}
	}

	void reverse() {

		if (nodeHead == nullptr) {
			
			return;
		}

		Node<T>* nodeCurr = nodeHead; //현재 노드 주소
		Node<T>* nodeNext = nullptr; //다음 노드 주소
		Node<T>* nodeRear = nullptr; //이전 노드 주소

		while (nodeCurr != nullptr) { //현재 노드가 nullptr이 될때 까지 루프

			nodeNext = nodeCurr->next; //next포인터를 curr의 다음 노드로 저장
			nodeCurr->next = nodeRear; //curr의 next를 포인터를 rear로 설정해 참조 방향을 역방향으로 변경
			nodeRear = nodeCurr; //rear포인터를 curr로 업데이트 후 다음 루프에서 사용
			nodeCurr = nodeNext; //curr포인터를 next로 업데이트
		}

		nodeHead = nodeRear; //새로운 헤드 지정
	}

	int getSize() const {

		return nSize;
	}

	bool isEmpty() const {

		return nodeHead->next == nullptr;
	}

	void debugDisplay() { //디버그용 출력 함수
		
		if (nodeHead == nullptr) {

			return;
		}

		Node<T>* nodeCurr = nodeHead;

		while (nodeCurr != nullptr) {

			std::cout << nodeCurr->data << std::endl;
			nodeCurr = nodeCurr->next;
		}
	}
};

 

 

 

주요 특징

 

1. 노드로 구성 : 단방향 연결 리스트는 노드(Node)라고 불리는 요소로 구성된다.

(각 노드는 데이터 필드(data filed)와 다음 노드를 가리키는 포인터를 포함함)

 

2. 단방향 : 각 노드가 다음 노드를 가리키는 링크만 가지고 있으므로 한 방향으로만 이동한다.

(역방향 탐색이 불가능하다 오직 순방향 탐색만 가능!)

 

3. 동적 크기 : 노드를 동적으로 추가 또는 제거할 수 있으므로 배열과 다르게 크기가 미리 정해지지 않는다.

 

4. 메모리 효율 : 노드가 필요할 때만 생성하고 필요 없어지면 메모리에서 해제할 수 있다.

 

5. 중간 삽입 및 삭제 : 중간에 노드를 추가 또는 삭제할 경우 배열에 비해 효율이 높다.

(다만 해당 연산을 하기 위해선 이전 노드의 위치를 알고 있어야 한다.)

 

6. 노드 순회 : 첫 노드부터 시작해 다음 노드로 이동하면서 데이터를 처리하므로 배열과는 다르게 검색 시간이 오래 걸린다.

 

 

장점

 

1. 삽입 및 삭제의 효율성 : 단방향 연결 리스트는 특정 위치에 원소를 삽입하거나 삭제하는 작업이 빠르다.

 

2. 메모리 사용량 : 단방향 연결 리스트는 동적 메모리 할당을 사용하므로

데이터 요소를 저장하기 위한 메모리를 효율적으로 활용할 수 있으며 미리 크기를 정하지 않고 필요에 따라

노드를 추가할 수 있다.

 

3. 메모리 절약 : 데이터를 저장할 때 배열과 달리 불연속적인 메모리 공간을 필요로 하지 않으므로

메모리의 낭비를 줄일 수 있다.

 

단점

 

1. 랜덤 액세스의 어려움 : 연결 리스트는 배열과는 다르게 랜덤 액세스가 어려우며

특정 인덱스의 요소를 찾는 데 O(n)의 시간 복잡도를 가진다.

 

2. 메모리 오버헤드 : 노드마다 포인터가 필요하므로 배열에 비해 메모리 오버헤드가 있을 수 있다.

 

3. 순회 시간 : 연결 리스트를 순회하는 데 O(n)의 시간이 걸리며, 배열보다 순회에 더 많은 시간이 소요될 수 있다.

 

4. 역방향 액세스의 어려움 : 역방향으로 연결 리스트를 탐색하려면 이전 노드를 기억하고 있어야 하므로

단방향 연결 리스트에선 뒤의 노드를 참조하는 게 불가능한 건 아니지만 어렵다.