[C++] 36. 자료구조 : 링크드리스트(LinkedList)

1. 링크드리스트의 개념

// 연결 리스트 //
// 앞의 세 구조와 달리 메모리에 있는 데이터의 물리적배치를 사용하지 않는 데이터구조다.
// index나 위치보다 '참조 시스템'을 사용한다.
// 각 요소는 '노드'라는 것에 저장되며, 다음 노드연결에 대한 포인터 또는 주소가 포함된 또 다른 노드에 저장한다.
// 모든 노드가 연결된 때까지 반복이 돼서 노드의 연결로 이루어진 자료구조다.
// 장점 : 새로운 요소의 추가와 삭제가 용이하다. 메모리를 더 효율적으로 쓸 수 있어 대용량 데이터 처리에 적합하다.
// 단점 : 배열보다 메모리를 더 사용한다. 처음부터 끝까지 순회하기 때문에 원하는 값을 비효율적으로 처리한다.
// 사용예시) 음악 플레이어, 이미지 뷰어, 갤러리, 데이터를 연속적으로 빠르게 삽입 및 제거가 필요할 때
// 벡터외 연결리스트의 차이점은 '백터는 중간삽입시 원소를 밀어내지만, 리스트는 노드를 연결만 하기때문에 삽입 및 삭제 부분에서 시간복잡도의 우위를 가진다'입니다.

2. 링크드리스트과 벡터의 차이

리스트는 외부에서 보면 벡터와 완전히 동일하다. 벡터는 동적배열이므로 새 공간이 할당되고 데이터를 추가할때 추가하고 싶은 값 다음의 데이터들이 한칸씩 뒤로 옮겨지므로 연산이 많아져서 비효율적이다. 하지만 리스트는 노드만 연결하기때문에 벡터보다 시간복잡도면에서 우위를 갖는다.

 

***추가나 삭제가 빈번히 이루어질 대용량의 자료구조를 갖을때는 배열(arrayed list)보다 링크드리스트(Linked list)를 사용해야한다. 예시로 인벤토리를 구현할때는 인벤토리 내 개수가 한정적으로 딱 정해져있을땐 배열을 쓰는게 낫지만, 일반적인 경우의 인벤토리를 구현할때는 링크드리스트를 쓰는게 낫다.

연속적인 배열과 연결리스트의 차이점

3. 링크드리스트 만들기

(1) 노드 생성

#include <iostream>

using namespace std;

class Node
{
public:
	int value;
	Node* next = nullptr;
};

(2) 링크드리스트 선언부

- 큐와 스택과는 다르게 연결리스트는 노드들끼리 연결되어 있어 수많은 원소들 사이에 새로운 값을 추가하거나 삭제할 수 있는 기능이 존재한다. 

- 코드의 가독성과 성능을 증대시키기 위해 Node* At라는 해당 위치의 노드를 반환하는 함수를 추가한다!!

class LinkedList
{
private:
	Node* head = nullptr;
	Node* tail = nullptr;
	int size = 0;

public:
	void AddNode(int _value);				// 맨뒤에 추가
	void AddNode(int _value, int position);	// position위치에 추가
	void RemoveNode(int position);		    // position위치에 삭제
	int SerchValue(int value);				// value를 찾아 position반환
	void Show();							// 전체 출력
	int GetSize();							// size게터
	bool IsEmpty();							// 비어있는지 확인
	~LinkedList();							// 클래스소멸자
	Node* At(int position);					// 해당 위치의 노드를 반환
};

(3) Add함수

- 큐와 스택의 Add함수와 동일한 기능을 갖기때문에 구현하는 방식도 동일하다.

void LinkedList::AddNode(int _value)
{
	Node* newNode = new Node();
	newNode->value = _value;
	size++;

	if (IsEmpty())
	{
		head = newNode;
		tail = newNode;
	}
	else
	{
		tail->next = newNode;
		tail = newNode;
	}
};

(4) Add(int value, int position)함수

- 추가하고자 하는 원하는 값(value)을 원하는 위치(position)에 넣기 위한 함수이다.

- Node* At()라는 해당 위치의 노드를 반환하는 함수를 선언하여 추가하고자 하는 위치의 전 노드에 접근이 용이해진다.

void LinkedList::AddNode(int _value, int position)
{
	if (position > size)
	{
		AddNode(_value);
		return;
	}
	Node* newNode = new Node();
	newNode->value = _value;

	size++;
	Node* prevlnsertPos = At(position - 1);

	newNode->next = prevlnsertPos->next;
	prevlnsertPos->next = newNode;
};

(5) remove()함수

- 코드구현의 접근방식은 다음 그림과 같다.

~~~우리는 C를 지우고 싶다~~~

①prevRemovePtr는 처음에 head로부터 우리가 지우길 원하는 위치(그림상에서는 B)까지 이동해야한다

②removePtr = prevRemovePtr->next; C를 지울꺼니까 B의 다음 위치를 저장

③delete removePtr; 저장해둔 C를 지운다.

void LinkedList::RemoveNode(int position)
{
	Node* prevRemovePtr;
	Node* removePtr;

	prevRemovePtr = At(position - 1);
	removePtr = prevRemovePtr->next; 

	prevRemovePtr->next = removePtr->next;	// B가 D를 가리킨다
	delete removePtr;

};

(6) Node* At(int position) : 해당 위치의 노드를 반환하는 함수

- 링크드리스트의 구현을 위해 매우 유용한 개념이다!!

Node* LinkedList::At(int position)	// 해당 위치의 노드를 반환
{
	if (position <= 0)
	{
		return head;
	}
	else if (position >= size)
	{
		return tail;
	}
	else
	{
		Node* current = head;
		for (int i = 0; i < position; i++)
		{
			current = current->next;
		}
		return current;
	}
}

(7)  int SerchValue(int value)

- 값(value)를 입력받아 위치(position)를 반환하는 함수 

int LinkedList::SerchValue(int value)
{
	int position = 0;
	Node* current = head;
	for (int i = 0; i < size; i++)
	{
		if (value == current->value) { position = i; break; }
		else { position = -2147483647; }
		current = current->next;
	}
	return position;
};

(8) void Show(), int GetSize(), bool IsEmpty()

- 큐와 스택에서도 등장했던 함수들

- 노드 전체를 출력하는 함수인 Show(), 사이즈를 반환하는 게터함수인 GetSize(), 빈공간을 확인하는 IsEmpty().

void LinkedList::Show()
{
	Node* current = head;
	while (current != nullptr)
	{
		cout << current->value << endl;
		current = current->next;
	}
};
int LinkedList::GetSize()
{
	return size;
};
bool LinkedList::IsEmpty()
{
	if (head == nullptr)
	{
		return true;
	}
	else
	{
		return false;
	}
};
LinkedList::~LinkedList()
{
	Node* current = head;
	Node* temp;
	while (current != nullptr)
	{
		temp = current;
		current = current->next;
		delete temp;
	}
	delete current;
}

(9) main

void main()
{
	LinkedList intLinkedList;

	intLinkedList.AddNode(10);
	intLinkedList.AddNode(20);
	intLinkedList.AddNode(30);
	intLinkedList.AddNode(40);

	intLinkedList.AddNode(80, 2);

	intLinkedList.AddNode(100, 200);

	// intLinkedList.RemoveNode(2);

	// 0 1 2 3 중 i의 위치의 노드를 가져오는 함수(반복문이므로 전체출력)
	for (int i = 0; i < intLinkedList.GetSize(); i++)
	{
		cout << intLinkedList.At(i)->value << endl;
	}
}

출력 결과