연결리스트 - 3장,4장

연결리스트

1. 순차 리스트 - 배열을 기반으로 구현된 리스트 (C++에서는 std::array, std::vector등 비슷한 컨테이너가 존재)

2. 연결 리스트 - 메모리의 동적 할당을 기반으로 구현된 리스트 (C++에서는 std::list)

 

리스트 자료구조는 데이터를 나란히(선형) 저장한다. 그리고 중복된 데이터의 저장을 막지않는다.

(자료구조 중에서는 중복된 데이터의 저장을 허용하지 않는 경우도 있다. ex)이진 탐색 트리)

 

우선 순차 리스트를 살펴보자.

(여기서부터는 C가 아닌 C++로 구현합니다.)

 

#pragma once
template<typename T>
class Array final
{
public:
	Array();
	~Array();
	inline size_t GetSize() const;
	inline size_t GetCapacity() const;
	T& operator[](unsigned int idx) const;
	bool Remove(const T& target);
	bool push_back(T item);
	bool pop_back() const;
	
private:
	enum { MAX = 100 };
	T* ptr; 
	// 혹은 unique_ptr로 소멸자에서 따로 delete를 하지않게 하는방법.
	size_t m_size; // 현재 요소의 수
	size_t m_capacity; // 현재 배열의 용량
};

template<typename T>
Array<T>::Array() : m_size(0), m_capacity(MAX)
{
	ptr = new T[m_capacity]();
}
template<typename T>
Array<T>::~Array()
{
	delete[] ptr;
}
template<typename T>
size_t Array<T>::GetSize() const
{
	return m_size;
}
template<typename T>
size_t Array<T>::GetCapacity() const
{
	return m_capacity;
}
template<typename T>
bool Array<T>::push_back(T item)
{
	if (m_size >= MAX)
		return false;
	*(ptr + m_size) = item;
	++m_size;
	return true;
}
template<typename T>
bool Array<T>::pop_back() const
{
	if (m_size < 0)
		return false;
	--m_size;
	return true;
}
template<typename T>
T& Array<T>::operator[](unsigned int i) const
{
	return ptr[i];
}
template<typename T>
bool Array<T>::Remove(const T& target)
{
	int i,j;
	for (i = 0; i < m_size; ++i)
	{
		if (ptr[i] == target)
		{
			for (j = i; j < m_size; ++j)
			{
				ptr[j] = ptr[j + 1];
			}
			return true;
		}
	}
	return false;
}

이렇듯 내부적으로 고정된 배열을 멤버로 가지고 있다.

 

배열 기반 리스트의 장점

: 데이터의 참조가 쉽다. 인덱스 값을 기준으로 어디든 한번에 참조가 가능하다.

배열 기반 리스트의 단점

: 배열의 길이가 초기에 결정되어야 한다. 변경이 불가능. 삭제의 과정에서 데이터의 이동(복사)가 빈번히 일어남.

 

링크드 리스트(노드기반의 리스트)

배열 기반의 리스트는 배열의 길이가 처음에 정해져야하는 정적인 특징이 존재한다.

그렇기에 리스트에 담을 데이터가 배열의 길이를 넘어서서 저장하지 못한다.(불가능한건 아니다. ex)std::vector->메모리 재할당. 하지만 메모리를 다시 만들고, 기존의 데이터를 복사한다음 무너뜨리는 일련의 과정이 자주 반복될 수 있다)

 

지금 배울 링크드 리스트는 노드기반의 리스트이며, 사용자가 데이터를 추가할 때 마다 노드를 동적으로 생성하고 그 안에 데이터를 저장한다. 그리고 그 노드들은 서로가 포인터 변수를 통해 연결되어있는 형태. 

배열과 같이 선형 자료구조이지만 메모리상에서 나란히 저장되는 배열과는 특성이 다르다.

(노드의 메모리는 서로 흩어져있음. 포인터로 서로가 연결 되어 있을 뿐. -> 데이터를 제거할때마다 앞으로 한칸 옮겨야하는 복사비용이 없다)

 

이렇게. 맨 처음 노드를 가리키는 헤드 포인터 변수가 존재하며 이것을 통해 우리는 처음 노드 부터 연결 되어있는 노드를 탐색할 수 있다.

 

이렇게 노드를 가리키는 포인터 변수는(노드끼리 연결된 포인터 변수를 지칭하는게 아님)각각 head,tail,cur이 존재하며 그것을 통해 어떻게 링크드 리스트를 만들지는 사용자의 마음이다.

 

링크드 리스트는 배열 자료구조와는 달리 인덱스 접근이 불가능하기에 탐색에 걸리는 시간은 O(n). 선형 시간복잡도를 가진다. 다만 배열과는 다르게 현재 내가 삭제하고싶은 어떤 노드를 가리키는 어떠한 포인터 변수가 있다고 가정하고

그 노드를 삭제할때 걸리는 시간은 배열보다 훨씬 줄어든다. (물론 그게아니라면 내가 원하는 값이 있는지 먼저 탐색하고 삽입/삭제를 해야하기에 걸리는 시간은 비슷하다)

 

중요한것은 링크드 리스트는 노드가 존재하고 그 노드는 데이터와 다음 노드를 가리키는 포인터 변수가 있으며 그것을 통해 서로가 이어지는 선형 구조.

 

나는 노드의 처음을 가리키는 head포인터 변수와 tail 포인터 변수를 통해 간단한 연결 리스트를 만들어보겠다.

#pragma once

class Node // int형 데이터를 담는 노드.
{
public:
	Node();
	Node(int data);
	~Node() = default;
	int GetData() const;
	void SetData(int item);
	Node* GetNextNode() const;
	void SetNextNode(Node* next);
private:
	int m_data;
	Node* m_next;
};

class LinkedList
{
public:
	LinkedList();
	~LinkedList();
	void push_back(int item);
	void push_front(int item);
	int GetlistSize() const;
	int pop_front();
	bool LFirst();
	bool LNext();
	Node* iterator() const; // 간단히 현재 위치를 반환.
private:
	Node* m_head;
	Node* m_tail;
	Node* m_cur;
	int	  m_size;
};

 

 

더미기반 단순 연결리스트로 구현하였다.

 

Node클래스는 자기자신에 데이터와 다음 노드를 가리킬 변수를 가지고 있고.

LinkedList클래스는 Node를 가리키는 포인터 변수3개와 현재 노드의 수를 저장하는 변수가 존재한다.

 

cpp 코드

#include "LinkedList.h"

Node::Node() : m_data(0), m_next(nullptr)
{

}
Node::Node(int data) : m_data(data), m_next(nullptr)
{

}
int Node::GetData() const
{
	return this->m_data;
}
void Node::SetData(int item)
{
	this->m_data = item;
}
Node* Node::GetNextNode() const
{
	return this->m_next;
}
void Node::SetNextNode(Node* next)
{
	this->m_next = next;
}

LinkedList::LinkedList() : m_head(new Node()),m_tail(m_head),m_cur(m_head),m_size(0)
{

}
LinkedList::~LinkedList()
{
	// 삭제
	for (int i = 0; i < m_size; ++i)
		pop_front();
}

void LinkedList::push_back(int item)
{
	Node* newNode = new Node(item);

	this->m_tail->SetNextNode(newNode);
	this->m_tail = newNode;
	++(this->m_size);
}
void LinkedList::push_front(int item)
{
	
	Node* newNode = new Node(item);

	newNode->SetNextNode(this->m_head->GetNextNode());
	this->m_head->SetNextNode(newNode);
	++(this->m_size);
	if (this->m_size == 1)
	{
		m_tail = newNode;
	}
}
int LinkedList::GetlistSize() const
{
	return this->m_size;
}
int LinkedList::pop_front()
{
	if (this->m_size <= 0)
		return -1;
	Node* popNode = this->m_head->GetNextNode();
	Node* popNextNode = popNode->GetNextNode();
	this->m_head->SetNextNode(popNextNode);
	int data = popNode->GetData();
	--(this->m_size);
	delete popNode;
	return data;
}

bool LinkedList::LFirst()
{
	if (this->m_size <= 0)
		return false;
	this->m_cur = this->m_head->GetNextNode();
	return true;
}
bool LinkedList::LNext()
{
	if (this->m_cur->GetNextNode() == nullptr)
		return false;
	this->m_cur = this->m_cur->GetNextNode();
	return true;
}

Node* LinkedList::iterator() const
{
	return this->m_cur;
}

 

링크드 리스트의 단점 : 배열과는 달리 임의접근이 불가능하므로 접근은 느리다. 특정 데이터를 찾으려면 처음부터 끝까지 순회를 해야하며 그 탐색은 포인터 연산으로 이루어져 배열보다 느림.

 

링크드 리스트의 장점 : 동적으로 메모리를 사용해 정적인 배열(벡터는 동적)과는 다르게 메모리를 효율적으로 사용가능.

또한 데이터의 삽입/삭제가 O(1)이다. (물론 그 데이터 노드의 위치를 알고있어야함)