[자료구조] 단방향 연결 리스트 (Singly Linked List)

단방향 연결 리스트는 데이터 구조 중 하나로, 각 노드가 데이터 요소와 다음 노드를 가리키는 포인터로 이루어진 구조이다. 배열과는 다르게 각 원소들이 직렬이 아닌 각각 따로 떨어져있다는 점이 특징이다. 이러한 성질은 데이터를 추가/삭제하는 상황에서 시간 복잡도를 더 적게 사용하기 때문에 효율적이다.

 

연결 노드

다양한 기능을 추가하기 전에 우선 연결 노드 자체를 구현해보자.

struct Node
{
	int item = 0;	  // <- 큰 데이터도 가능
	Node* next = nullptr;
}

Node 구조체는 다음과 같이 생겼다. 값을 저장할 변수를 가지고, 다음 Node를 가르킬 포인터 변수를 가진다.

 

 

다섯 개의 노드를 만들어보았다.

// ListArray와 비교
Node* first = nullptr; 
first = new Node; //First 라는 포인터가 Node의 주소를 가르키고 있다.
first->item = 1;
first->next = nullptr;

Node* second = nullptr;
second = new Node;
second->item = 2;
second->next = nullptr;

Node* third = nullptr;
third = new Node;
third->item = 3;
third->next = nullptr;

Node* fourth = nullptr;
fourth = new Node;
fourth->item = 4;
fourth->next = nullptr;

Node* fifth = nullptr;
fifth = new Node;
fifth->item = 5;
fifth->next = nullptr;

이렇게 만든 다섯 개의 노드의 연결 관계를 정의하고 싶다. 한 노드의 next가 다음 노드를 가르키게 하면 된다.

//// 연결 관계 만들어 주기
first->next = second;
second->next = third;
third->next = fourth;
fourth->next = fifth;
fifth->next = nullptr;

현재 위의 그림과 같은 상황이 만들어졌다.

 

시작 노드부터 끝 노드까지의 데이터를 출력하는 방법

// 반복문 이용 , 재귀 호출로도 가능하다.
Node* current = first;
while (current) { //current가 Null이 아닐 경우
    cout << *node << endl; // 연결 리스트의 데이터를 출력
    node = node->next; 	   // 다음 노드로 이동
}
cout << endl;

first 포인터가 가르키는 곳을 가르키는 current 포인터를 만든다. current 포인터가 가르키는 값이 null이면 종료되는 while문을 돌린다. current 포인터가 가르키는 값이 null이 아니라는 조건이 성립됐기에 current 포인터 값을 출력하고 다음 노드로 넘어가고 있다.

 

 

모든 데이터 삭제

while (current) {
    Node* tmp = current;
    current = current->next;
    delete current;
}

임시 변수에 현재(current) 포인터를 저장하고, 현재는 다음 노드로 넘어간다. 이후 임시 변수를 삭제하는 방식으로 모든 데이터를 삭제하는 것이 가능하다.

 

 

 

단방향 연결 리스트 구현 

이제 연결 리스트에 다양한 기능을 구현해보는 시간을 가져볼 것이다. main() 함수를 보면서 어떤 기능을 구현할 것인지 살펴보자.

int main()
{
    SinglyLinkedList<int> list;

    //맨 앞에 노드 추가
    list.PushFront(3);
    list.PushFront(2);
    list.PushFront(1);
    //맨 뒤에 노드 추가
    list.PushBack(4);
    list.PushBack(5);
    //모든 노드 출력
    list.Print();

    //노드 순서 뒤집기
    list.Reverse();
    list.Print();

    //특정 노드 찾기
    SinglyLinkedList<int>::Node* temp = list.Find(3);

    //특정 노드 뒤에 노드 삽입하기
    list.InsertBack(temp, 1000);
    list.Print();

    list.InsertBack(temp, 50);
    list.Print();

    //특정 노드 삭제하기
    list.Remove(temp);
    list.Print();

	for (int i = 0; i < 5; i++)
	{
    	//맨 앞의 노드 삭제하기
		list.PopFront();
		list.Print();

		//맨 뒤의 노드 삭제하기
		list.PopBack();
		list.Print();
	}
	return 0;
}

 

맨 앞에 노드 추가하기

first_가 null인 경우와 아닌 경우를 나눠서 구현해야하지만 구현하다보면 둘의 코드가 똑같다는 사실을 알 수 있다.

void PushFront(T item)
{
    // 새로운 노드 만들기
    Node* temp = new Node;
    temp->item = item;
    // 연결 관계 정리
    temp->next = first_;
    first_ = temp;
}

 

 

맨 뒤에 노드 추가하기

만약 first_가 null인 경우는 그냥 PushFront()를 호출하면 된다. 참고로 조건문에 null이 들어가면 false이다. 그 외에 경우에는 노드를 마지막 노드로 이동시킨 후에 마지막 노드가 null이 아닌 새로 들어온 노드를 가르키게 하면 된다.

void PushBack(T item)
{
    if (first_)
    {
        Node* lastNode = first_;
        while (lastNode->next) {
            lastNode = lastNode->next;
        }
        Node* temp = new Node;
        temp->item = item;
        temp->next = nullptr;
        lastNode->next = temp;
    }
    else
    {
        PushFront(item);
    }
}

한 노드가 가르키는 다음 노드가 null일 때까지 루프를 돌려서 마지막 노드를 찾는다. 이후 새로운 노드를 만든 후에 새로운 노드는 null을 가르키게하고 찾은 마지막 노드는 새로운 노드를 가르키게 한다.

고양이 뒷모습 같다 ㅎㅎ

노드 순서 뒤집기

이게 솔직히 많이 어렵다. 말로 설명을 잘할 수 있을지 모르겠는데 .. 일단 이건 그림을 먼저 보자.

void Reverse()
{
    Node* current = first_;
    Node* prev = nullptr;	

    while (current) {
        Node* temp = prev;
        prev = current;
        current = current->next;
        prev->next = temp;
    }

    first_ = prev;
}

일단 current 라는 포인터는 시작 노드를 가르키고 prev는 아무것도 가르키지 않고 있다. current가 nullptr이 아닐 때까지 반복문이 실행되는데 prev의 주소를 임시(temp) 변수가 가르킨다. 그 이후 prev는 current를 따라가고, current는 다음 노드로 넘어간다. prev는 임시 변수가 가르키는 값을 가르킨다. 

 

current가 null이 되서 while문이 종료되면 first_는 prev를 가르키는데 이떄 이미 뒤집기가 완료된 상황이다. 

 

 

 

특정 노드 찾기

처음 노드에서 다음 노드로 넘어가면서 만약 넘어간 노드가 찾으려는 노드가 갖고 있는 값과 같은 값을 가지고 있다면 while문을 종료하는 식으로 구현할 수 잇다.

Node* Find(T item)
{
    Node* current = first_;
    while (current) {
        if (current->item == item) {
            return current;}
        current = current->next;
    }
    return current;
}

 

특정 노드 뒤에 노드 삽입하기

임시 노드를 만든 다음에 이전 노드가 가르키던 노드를 임시 노드가 가르키게 하고 이전 노드는 임시 노드를 가르키게 하는 방식으로 구현할 수 있다.

void InsertBack(Node* node, T item)
{
    if (IsEmpty()) //기존에 노드가 없는 상황에 대한 예외처리
    {
        PushFront(item);
    }
    else
    {
        Node* temp = nullptr;
        temp = new Node;
        temp->next = node->next;
        temp->item = item;
        node->next = temp;
    }
}

 

 

특정 노드 삭제하기

삭제하려는 노드 이전의 노드를 찾는다. 이전 노드가 삭제하려는 노드가 가르키는 노드를 가르키게 하고 이후 삭제하려는 노드를 삭제한다.

void Remove(Node* n)
{
    assert(first_);

    //노드가 1개일 때 예외처리
    if (first_ == n)
    {
        first_ = first_->next;
        delete n;
        return;
    }

    Node* temp = first_;
    while (temp->next) { //temp의 next가 유효하냐를 체크하고 있다.
        if (temp->next == n) {
            break;
        }
        temp = temp->next;
    }
    temp->next = n->next;
    delete n;
}

 

 

맨 앞의 노드 삭제

시작 노드가 가르키는 다음 노드를 가르키는 포인터를 만들고 시작 노드를 삭제한다. 이후 시작 포인터를 다음 노드를 가르키는 포인터가 가르키는 노드를 가르키게 한다.

void PopFront()
{
    //노드가 비어있을 때 예외처리
    if (IsEmpty())
    {
        using namespace std;
        cout << "Nothing to Pop in PopFront()" << endl;
        return;
    }
    assert(first_);
    Node* temp = first_->next;
    delete first_;
    first_ = temp;
}

맨 뒤의 노드 삭제

맨 뒤의 노드 이전 노드를 찾는다. 이전 노드가 가르키는 노드를 임시 노드에 저장하고 이전 노드는 NULL을 가르키게 한다. 이후 임시 노드를 삭제하면 된다.

	void PopBack()
	{
		if (IsEmpty())
		{
			using namespace std;
			cout << "Nothing to Pop in PopBack()" << endl;
			return;
		}
        // 노드가 1개인 경우에 대한 예외처리
		if (first_->next == nullptr) {
			delete first_;
			first_ = nullptr;
			return;
		}
		// 맨 뒤에서 하나 앞의 노드를 찾아야 합니다.
		assert(first_);
		Node* temp = first_;
		while (temp->next->next) {
			temp = temp->next;
		}
		Node* temp2 = temp->next;
		temp->next = nullptr;
		delete temp2;
	}

재밌는 포인트 node->next->next 이런 연산이 가능하다 !

 

 

마치며 ... 평생 그려볼 노드 오늘 다 그린 것 같다 :)