리스트(List)

리스트란?

리스트(List) 또는 선형 리스트(Linear list)는 자료를 정리하는 방법 중 하나이다. 우리는 일상 생활에서도 많은 리스트를 사용하고 있다. 예를 들어, 오늘 해야 할 일이나 슈퍼에서 사야할 물건들을 리스트로 정리한다.

 

리스트에는 보통 항목들이 차례대로 정리되어 있다. 리스트의 항목들은 순서 또는 위치를 가진다. 리스트는 기호로 다음과 같이 표현한다.

 

L = (item(0), item(1), item(2), ..., item(n-1))

 

다음은 대표적인 리스트의 예이다.

 

• 사고 싶은 물건들 : (스마트폰, 자전거, 가방, ..., 신발)

• 이번 주에 해야 할 일들 : (자료구조 숙제, 아르바이트, 집 청소, ..., 빨래)

• 가고 싶은 여행지들 : (파리, 지리산, 마라도, ..., 안면도)

• 임의의 다항식의 각 항들 : (5x^3, 3x^2, 2x, 8)

리스트는 다른 선형 자료구조(스택, 큐)와 다르게 전단(Front) 혹은 후단(Rear)에 제한되어 있지 않고 중간에 삽입하거나 삭제하는 등의 작업을 할 수 있다. 따라서 선형 자료구조들 중에서 가장 활용이 자유롭다, 물론 편리한 만큼 고려해야 할 점들도 많다.

---

구현

싱글 링크드 리스트(단일 연결 리스트)와 더블 링크드 리스트(이중 연결 리스트) 두가지를 구현해볼 것이다. 

 

미리 컴파일 된 헤더는 다음과 같다.

// pch.h

#ifndef PCH_H
#define PCH_H

// 여기에 미리 컴파일하려는 헤더 추가
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <iostream>
using namespace std;

#include "DataType.h"

// 단일 리스트로 사용할건지 이중 리스트로 사용할건지 
#define Single
//#define Double

#endif //PCH_H

데이터 구조체는 다음과 같다.

typedef struct _data
{
	int number;

public:
	void operator=(const _data& other)
	{
		number = other.number;
	}
	bool operator==(const _data& other)
	{
		return number == other.number;
	}
	bool operator < (const _data& other)
	{
		return number < other.number;
	}
	bool operator > (const _data& other)
	{
		return number > other.number;
	}
}DATA;

 

 

기능

기본적으로 제공하는 기능은 다음과 같다.

 

• 데이터 삽입 : 데이터의 숫자 오름차순으로 자동으로 삽입된다. 

• 데이터 삭제 : 원하는 삭제 데이터를 입력하면 리스트에 존재하는 경우 삭제한다.

• 전체 삭제 : 리스트에 있는 모든 데이터를 삭제한다.

• 전체 출력 : 리스트에 있는 모든 데이터를 출력한다.

• Empty 검사 : 리스트가 비어 있는지를 검사한다.

 

그림과 같은 방식으로 삽입, 삭제를 하며 노드끼리 잇고 있는 노드 주소포인터를 삽입, 삭제시 알맞은 주소를 대입해줘야 한다. 이 작업이 잘못되는 경우 삽입, 삭제 노드부터 시작되는 모든 노드들 혹은 최악의 경우에는 노드의 전체 데이터를 잃어버릴 수 있다.

 

구조

구조를 그림으로 표현

구조는 다음과 같다. Linked List라는 부모 클래스에 단일과 이중 링크드 리스트가 상속받는다. 그러면 본격적으로 코드로 한번 살펴 보도록 하겠다.

 

LinkedList 클래스

// LinkedList.h

#pragma once
class LinkedList
{
public:
	LinkedList() {}
	virtual ~LinkedList() {}

public:
	virtual void Add(DATA& data) = 0;
	virtual void Delete(DATA& data) = 0;
	virtual void Clear() = 0;
	virtual void Print() = 0;
	virtual bool CheckEmpty() = 0;
};

기본적으로 제공하는 모든 리스트의 기능들을 순수 가상함수로 가지고 있어 상속받은 클래스에서 오버라이딩 하여 사용하도록 하였다. 헤더만 사용한다.

 

UserInterface 클래스

// UserInterface.h

#pragma once
#include "LinkedList.h"

class UserInterface
{
public:
	UserInterface();
	~UserInterface();
public:
	void Initialize();
	void Logic();
	void PrintMenu();
	int InputAndRun();
private:
	LinkedList* m_linkedList = nullptr;
};

UserInterface 클래스는 콘솔 창에 메뉴를 띄우고 리스트를 알맞은 종류의 리스트로 동적할당하여 사용자가 원하는 기능들을 메서드 호출하는 작업을 한다.

// UserInterface.cpp

#include "pch.h"
#include "UserInterface.h"
#include "SingleLinkedList.h"
#include "DoubleLinkedList.h"

UserInterface::UserInterface()
{
}

UserInterface::~UserInterface()
{
	delete m_linkedList;
	m_linkedList = nullptr;
}

void UserInterface::Initialize()
{
// 알맞는 리스트로 동적할당한다. 
#ifdef Single
	m_linkedList = new SingleLinkedList;
#endif
#ifdef Double
	m_linkedList = new DoubleLinkedList;
#endif

// 만약 동적할당이 제대로 이루어지지 않았다면 프로그램을 중단시킨다.
	assert(m_linkedList);
}

void UserInterface::Logic()
{
// 콘솔창에 메뉴 및 기능 실행 등에 대한 로직이 돌아간다.
	while (1)
	{
    	// 메뉴화면을 출력한다.
		PrintMenu();
        // 사용자가 원하는 작업을 수행한다.
        // 만약 종료를 누르면 루프문을 빠져나온다.
		if (-1 == InputAndRun())
			break;
	}
}

void UserInterface::PrintMenu()
{
	cout << "========================================================" << endl;
	cout << "1. Add  2. Delete  3. Clear  4. Print  5. Exit" << endl;
	cout << "Input? ";
}

int UserInterface::InputAndRun()
{
	int input = 0;
	DATA data;
	cin >> input;
	switch (input)
	{
	case 1: 
		cout << "Input Number to add. Number? ";
		cin >> data.number;
		m_linkedList->Add(data);
		break;
	case 2:
		cout << "Input Number to delete. Number? ";
		cin >> data.number;
		m_linkedList->Delete(data);
		break;
	case 3: m_linkedList->Clear(); break;
	case 4: m_linkedList->Print(); break;
	case 5: return -1;
	default: cout << "Wrong Input! Try Again!" << endl; break;
	}

	return 0;
}

 

Main()

캡슐화 되어 있어 매우 간단하게 리스트를 실행시킬 수 있다.

#include "pch.h"
#include "UserInterface.h"

int main()
{
    UserInterface ui;
    ui.Initialize();
    ui.Logic();
}

 

단일 연결 리스트(SingleLinkedList)

맨 앞을 알 수 있도록 Head 노드를 두었다. Head 노드에 들어가는 데이터는 없으며 그 다음 노드 부터 데이터가 들어가 있는 시작 노드이다.

 

노드 구조체는 다음과 같다.

// DataType.h

typedef struct _singleNode
{
	DATA data;
	_singleNode* next;
}SNODE;

 

 

SingleLinkedList 클래스

// SingleLinkedList.h

#pragma once
#include "LinkedList.h"

class SingleLinkedList
	: public LinkedList
{
public:
	SingleLinkedList();
	virtual ~SingleLinkedList();

public:
	virtual void Add(DATA& data);
	virtual void Delete(DATA& data);
	virtual void Clear();
	virtual void Print();
	virtual bool CheckEmpty();

private:
	SNODE m_head;
};

LinkedList 클래스를 상속받으며 단일 연결 리스트로 시작을 알기위한 Head 노드를 멤버변수로 가지고 있다.

// SingleLinkedList.cpp
#include "pch.h"
#include "SingleLinkedList.h"

SingleLinkedList::SingleLinkedList()
{
	m_head.next = nullptr;
}

SingleLinkedList::~SingleLinkedList()
{
	Clear();
}

void SingleLinkedList::Add(DATA& data)
{
	// 추가할 데이터를 가진 새로운 노드를 만든다.
	SNODE* newNode = new SNODE;
	memset(&newNode->data, 0, sizeof(DATA));
	newNode->data = data;
	newNode->next = nullptr;

	// head의 next가 비어있는 경우 (empty인 경우)
	if (nullptr == m_head.next)
	{
		// head의 next에 새로 만든 노드의 주소를 넣는다.
		m_head.next = newNode;
	}
	else
	{
		// head 노드에서 부터
		SNODE* node = &m_head;

		// 추가할 알맞는 노드까지 찾는다.
		while (nullptr != node->next)
		{
			// 데이터 값이 새로운 데이터 값과 같은 경우
			// 혹은 다음 데이터 값이 더 큰 경우
			if (node->data == newNode->data ||
				node->next->data > newNode->data)
			{
				// 중간에 삽입 해준다.
				newNode->next = node->next;
				node->next = newNode;
				return;
			}
		
			node = node->next;
		}
		// 끝에 도달한 경우
		node->next = newNode;
	}
}

void SingleLinkedList::Delete(DATA& data)
{
	// 비어 있는지 검사한다.
	if (true == CheckEmpty())
	{
		cout << "Empty!" << endl;
		return;
	}

	// Head 노드부터
	SNODE* node = &m_head;
	// 중간 삭제시 노드를 이어 붙이기 위해 전 노드 주소가 필요하다.
	SNODE* preNode = nullptr;
	while (nullptr != node->next)
	{
		preNode = node;
		node = node->next;

		// 삭제하려는 값이 들어간 노드를 찾은경우
		if (data == node->data)
		{
			// 삭제하려는 노드간 연결을 끊고
			// 삭제하기 전 노드와 다음 노드를 이어붙인다.
			preNode->next = node->next;
			node->next = nullptr;
			// 노드를 삭제한다.
			delete node;
			node = nullptr;
			return;
		}	
	}
}

void SingleLinkedList::Clear()
{
	// Head 노드부터 순회 돌면서 삭제작업을 한다.
	SNODE* node = &m_head;
	SNODE* eraseNode = nullptr;
	node = node->next;
	while (nullptr != node)
	{
		eraseNode = node;
		node = node->next;
		delete eraseNode;
		eraseNode = nullptr;
	}
	m_head.next = nullptr;
}

void SingleLinkedList::Print()
{
	// 노드의 데이터를 모두 출력한다.
	if (true == CheckEmpty())
	{
		cout << "Empty!" << endl;
		return;
	}

	SNODE* node = &m_head;
	cout << "(HEAD) ---> ";
	node = node->next;
	while (nullptr != node)
	{
		cout << node->data.number << " ---> ";
		node = node->next;
	}
	cout << "nullptr" << endl;
}

bool SingleLinkedList::CheckEmpty()
{
	if (nullptr == m_head.next)
		return true;
	else
		return false;
}

 

출력 값 

 

이중 연결 리스트(DoubleLinkedList)

맨 앞과 맨 뒤를 알 수 있도록 Head와 Tail 노드를 두었다. 그리고 단일 연결 리스트와는 다르게 다음 노드 뿐만 아니라 이전 노드도 노드끼리 서로 잇고 있다는 특징이 있다.

 

노드로 사용되는 구조체는 다음과 같다.

// DataType.h

typedef struct _doubleNode
{
	DATA data;
	_doubleNode* next;
	_doubleNode* prev;
}DNODE;

 

DoubleLinkedList 클래스

// DoubleLinkedList.h

#pragma once
#include "LinkedList.h"

class DoubleLinkedList
	:public LinkedList
{
public:
	DoubleLinkedList();
	virtual ~DoubleLinkedList();

public:
	virtual void Add(DATA& data);
	virtual void Delete(DATA& data);
	virtual void Clear();
	virtual void Print();
	virtual bool CheckEmpty();

private:
	DNODE m_head;
	DNODE m_tail;
};

단일 연결 리스트와 같이 LinkedList 클래스를 상속받으며 Head 노드와 Tail 노드를 멤버변수로 가지고 있다.

 

// DoubleLinkedList.cpp

#include "pch.h"
#include "DoubleLinkedList.h"

DoubleLinkedList::DoubleLinkedList()
{
	// tail과 head를 서로 연결해준다.
	// 비어 있다.
	m_head.next = &m_tail;
	m_tail.prev = &m_head;

	m_head.prev = nullptr;
	m_tail.next = nullptr;

}

DoubleLinkedList::~DoubleLinkedList()
{
	Clear();
}

void DoubleLinkedList::Add(DATA& data)
{
	// 추가할 데이터를 가진 새로운 노드를 만든다.
	DNODE* newNode = new DNODE;
	newNode->data = data;
	newNode->prev = nullptr;
	newNode->next = nullptr;

	// 만약 Empty인 경우
	if (&m_tail == m_head.next &&
		&m_head == m_tail.prev)
	{
		m_head.next = newNode;
		newNode->prev = &m_head;
		m_tail.prev = newNode;
		newNode->next = &m_tail;
	}
	else
	{
		// head 노드에서 부터
		DNODE* node = &m_head;

		// 추가할 알맞는 노드까지 찾는다.
		while (&m_tail != node->next)
		{
			// 데이터 값이 새로운 데이터 값과 같은 경우
			// 혹은 다음 데이터 값이 더 큰 경우
			if (node->data == newNode->data ||
				node->next->data > newNode->data)
			{
				// 중간에 삽입 해준다.
				newNode->next = node->next;
				node->next->prev = newNode;
				node->next = newNode;
				newNode->prev = node;
				return;
			}

			node = node->next;
		}

		// 끝에 도달한 경우
		// 그냥 tail이 끝이니 그것을 이용하여 추가하면 된다.
		newNode->next = &m_tail;
		newNode->prev = m_tail.prev;
		m_tail.prev->next = newNode;
		m_tail.prev = newNode;
	}
}

void DoubleLinkedList::Delete(DATA& data)
{
	// 비어 있는지 검사한다.
	if (true == CheckEmpty())
	{
		cout << "Empty!" << endl;
		return;
	}

	// Head 노드부터
	DNODE* node = &m_head;
	while (&m_tail != node->next)
	{
		node = node->next;

		// 삭제하려는 값이 들어간 노드를 찾은경우
		if (data == node->data)
		{
			// 삭제하기 전 노드와 다음 노드를 서로 이어붙인다.
			node->prev->next = node->next;
			node->next->prev = node->prev;
			// 노드를 삭제한다.
			delete node;
			node = nullptr;
			break;
		}
	}
}

void DoubleLinkedList::Clear()
{
	// Head 노드부터 순회 돌면서 삭제작업을 한다.
	DNODE* node = &m_head;
	DNODE* eraseNode = nullptr;
	while (&m_tail != node->next)
	{
		node = node->next;
		eraseNode = node;
	}
	m_head.next = &m_tail;
	m_tail.prev = &m_head;
}

void DoubleLinkedList::Print()
{
	// 노드의 데이터를 모두 출력한다.
	if (true == CheckEmpty())
	{
		cout << "Empty!" << endl;
		return;
	}

	DNODE* node = &m_head;
	cout << "HEAD <----> ";
	while (&m_tail != node->next)
	{
		node = node->next;
		cout << node->data.number << " <-----> ";
	}
	cout << "TAIL" << endl;
}

bool DoubleLinkedList::CheckEmpty()
{
	if (&m_tail == m_head.next ||
		&m_head == m_tail.prev)
		return true;
	else
		return false;
}

 

출력 값