[자료구조] 연결 리스트(Linked list)

kuku·2023년 2월 4일

CS 스터디

목록 보기

8/18

📖연결 리스트

연결 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다. 각 노드의 포인터가 이전 노드나 다음 노드와 현재 노드를 연결해주는 역할을 한다.

연결 리스트는 배열과 달리 연속적인 메모리 위치에 데이터가 저장되지 않기 때문에 포인터를 가지고 다른 노드와 연결한다. 이러한 특징으로 인해 배열에서 흔히 사용하는 인덱싱 기능이 불가하고, 특정 위치의 데이터를 찾기 위해서 O(n)의 시간이 요구된다. 그러나, 포인터만 원하는 노드에 새로 연결해주면 이전 노드나 다음 노드가 무엇이었는지 수정할 수 있기 때문에 데이터의 추가와 삭제가 O(1) 시간에 가능하다.

📁단일 연결 리스트

단일 연결 리스트는 가장 기본적인 형태의 연결 리스트로, 각 노드에 데이터를 저장할 공간과 포인터를 저장할 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.

c++에서 구조체를 사용하여 노드를 구현해보면 다음과 같다.

struct Node
{
	int data;
	Node* next;
} node[10000]

int nodeCnt;
Node* head;

Node* getNode(int data)
{
	node[nodeCnt].data = data;
	node[nodeCnt].next = nullptr;
	return &node[nodeCnt++];
}

Node* getLoc(int data)
{
	Node* temp = head;

	for (int i = 0; i < data; i++)
	{
		if (temp->next)
		{
			temp = temp->next;
		}
		else
		{
			return nullptr;
		}
	}

	return temp;
}

void insert(Node* loc)
{
	int num, in_data;
	Node* temp;
	cin >> num;

	if (loc->next) //맨마지막 원소가 아님
	{
		for (int i = 0; i < num; i++)
		{
			cin >> in_data;
			temp = getNode(in_data);
			temp->next = loc->next;
			loc->next = temp;
			loc = temp;
		}
	}
	else //loc가 맨마지막 원소
	{
		for (int i = 0; i < num; i++)
		{
			cin >> in_data;
			temp = getNode(in_data);
			loc->next = temp;
			loc = temp;
		}
	}
}

void del(Node* loc)
{
	int num;
	cin >> num;

	for (int i = 0; i < num; i++)
	{
		if (loc->next == nullptr) //loc가 마지막 원소
		{
			return;
		}
		loc->next = loc->next->next;
	}
}

void add()
{
	Node* temp = head;
	Node* n_ptr;
	int num, add_data;
	
	while (temp->next)
	{
		temp = temp->next;
	}

	cin >> num;
	for (int i = 0; i < num; i++)
	{
		cin >> add_data;
		n_ptr = getNode(add_data);
		temp->next = n_ptr;
		temp = n_ptr;
	}
}

연결 리스트의 최대 길이는 10000이며, 데이터는 정수값을 저장한다고 가정한다.