[자료구조] 연결리스트

배열 vs 연결리스트

리스트는 기본적인 연산 삽입, 삭제, 검색 등과 더불어 리스트를 대표하는 두 가지 방법은 배열과 연결리스트입니다. 

 

배열의 단점은 크기가 고정되어 있어 reallocation이 필요하며 리스트의 중간에 원소를 삽입하거나 삭제할 경우 다수의 데이터를 옮겨야 하는 단점이 있습니다.

 

하지만 연결리스트 같은 경우는 다른 데이터의 이동없이 중간에 삽입이나 삭제가 가능하며, 길이의 제한이 없습니다. 하지만 랜덤 엑세스는 불가능합니다. 

 

배열은 크기가 동일한 데이터를 저장하는 자료구조이기 때문에 한 칸의 크기는 다 같습니다. 100번째 원소에 위치를 간단한 상수로 계산할 수 있기 때문에 첫 번째나 100번째나 덧셈 한번 더한다는 차이밖에 없기에 랜덤 엑세스가 가능합니다. 

 

중간에 데이터를 삽입할 일이 많으면 연결리스트가 낫지만 그것이 아니고서는 배열이 낫다고 볼 수 있습니다.

배열로 저장하면 메모리의 연속된 위치에 순서로 저장하는 것입니다. 

 

연결리스트를 보면 첫 번째 노드가 저장된 주소는 기억하고 있어야 하며 두 번째 데이터부터는 두 번째 데이터를 첫 번째 데이터와 함께 저장을 해놓는 구조입니다. 

 

연결리스트가 가진 두 가지 장점은 길이의 제한이 없고 다른 데이터의 이동없이 중간의 삭제나 삽입이 가능하다는 것입니다. 특정한 위치에 저장되어야 하는 것이 없기 때문에 길이의 제한이 없는 것이며 연결리스트는 빈칸을 찾아서 저장하고 그 주소를 현재의 마지막 데이터에 써주기만 하면 되는 것입니다. 

 

삽입이나 삭제의 경우에도 새로운 데이터를 삽입하거나 삭제할 때 다른 데이터가 옮겨다녀야 할 이유는 별로 없습니다. 

예를들어 Thursday를 삽입하고 싶다면 이 Thursday가 어디에 저장되는지는 별로 중요하지 않고 tuesday 다음 데이터가 107번지에서 108번지로 바꿔주기만 하면 되고 그 다음 Friday이기에 107번지로 두번 자연스럽게 추가가 된 것을 볼 수 있습니다. 

 

노드

데이터와 다음 데이터의 주소를 저장하는 하나의 데이터

 

각각의 노드는 필요한 데이터 필드와 하나 혹은 그 이상의 링크 필드로 구성되어 있으며 링크 필드는 다음 노드의 주소를 저장합니다. 첫 번째 노드의 주소는 따로 저장해야 합니다.

 

연결리스트의 첫 번째 노드의 주소는 따로 저장해야 하며 절대 잃어버려서는 안됩니다. 

 

이 Node는 특별한 경우가 아니면 동적으로 생성해주는 특성을 가지고 있습니다. 

 

struct Node {
	string data;

	Node* next;

};

Node* head = nullptr;

다음 노드의 주소를 저장하며 자신과 동일한 구조체에 대한 포인터를 멤버로 가진다는 의미에서 "자기참조형 구조체"라고 부르기도 합니다. 다음 노드가 없을 경우 nullptr을 저장합니다.

 

연결 리스트의 첫 번째 노드의 주소를 저장할 포인터는 head입니다. 

 

struct node
{
	char* data;
	struct node* next;
};
typedef struct node Node;
Node* head = NULL;

 

 

int main()
{
	Node* heat = new Node;
	head->data = "Tuesday";
	head->next = nullptr;

	Node* q = new Node;
	q->data = "Thursday";
	q->next = nullptr;
	head->next = q;

	q = new Node;
	q->data = "Monday";
	q->next = head;
	head = q;

	Node* p = head;
	while(p!=nullptr)
	{
		cout << p->data << endl;
		p = p->next;
	}
}