[C++ | 연결 리스트] 스택, 큐, 리스트

---

[리스트]

• 리스트에는 항목들이 차례대로 저장되어 있음
• 리스트의 항목들은 순서 또는 위치를 가짐 (버킷 리스트, 요일들)
• 스택, 큐도 넓게 보면 리스트의 일종

 

[연결리스트]

• 자료를 저장하고 있는 노드와 다음 자료의 위치를 가리키는 포인터로 구성
• 동적으로 크기가 변함
• 삭제, 삽입 시 데이터 이동할 필요가 없음

 

 

 

[배열과 연결리스트]

배열	연결리스트
인덱스로 자료에 접근하므로 탐색시간이 빠름	특정 노드에 접근하기 위해 이전 노드들을 탐색해야 하므로 탐색시간이 오래 걸림 ( 시간 복잡도 : O(n) )
임의의 원소를 삽입하거나 삭제할 때 많은 양의 원소를 이동시켜야함	노드의 이동이 불필요하여 삽입, 삭제가 용이함 ( 시간 복잡도 : O(1) )
자료의 크기가 배열의 크기에 제약을 받음	자료의 삽입 / 삭제가 동적 할당에 의해 이루어져서 기억장소의 낭비를 최소화 할 수 있음
메모리 상 배치가 연속적	메모리 상 배치가 불연속적

 

 

[연결리스트로 하는 스택 구현]

기본 코드

#include <iostream>
using namespace std;

bool isEmpty(); // top이 NULL인지 확인
void Push(int data);

struct NODE
{
	NODE* next; // 앞 노드의 주소
	int data; // 담고 있는 데이터
};
NODE* s_top = NULL; // 지금의 top

bool isEmpty()
{
	if (s_top == NULL) return true;

	return false;
}

 

 

스택의 삽입

 

- 노드 D의 링크 필드가 노드 C를 가리키도록 한다

- 헤더 포인터 Top이 노드 D를 가리키도록 한다

 

 

void Push(int data)
{
	NODE* temp = new NODE;
	temp->next = NULL;
	temp->data = data;
	if (isEmpty()) // top이 NULL이면
		s_top = temp; // 나를 top으로 설정
	else // top이 있으면
	{
		temp->next = s_top; // 앞 노드를 지금의 top으로 설정
		s_top = temp; // 나를 top으로 설정
	}
}

 

 

스택의 삭제

 

 

- 포인터 변수 p가 노드 C를 가리키도록 한다

- 헤더 포인터 Top이 B를 가리키도록 한다

- 마지막으로 포인터 p를 삭제한다

 

 

int Pop()
{
	if (IsEmpty()) return NULL; // Pop할게 없으면 NULL 반환

	NODE* delTemp = top; // 맨 위에 있는 얘를 가져와서
	int rData = delTemp->data; // 반환해줄 데이터를 가져오고
	top = delTemp->next; // Top을 지워줄 노드 앞으로 바꾸고
	delete delTemp; // 맨 위 노드를 지운다
	return rData;
}

 

 

[연결리스트로 하는 큐 구현]

 

기본 코드

#include <iostream>
using namespace std;

bool IsEmpty(); // 큐가 비었는지
void EnQueue(int data);
int DeQueue();

struct NODE
{
	NODE* next; // 내 앞 노드의 주소
	int data; // 가지고 있는 데이터
};
NODE* front = NULL; // 맨 앞
NODE* rear = NULL; // 맨 뒤
int qCount = 0; // 큐의 사이즈

bool IsEmpty()
{
	if (front == NULL || rear == NULL) return true;

	return false;
}

 

 

큐의 삽입

void EnQueue(int data)
{
	NODE* temp = new NODE; // 넣을 노드를 만들고
	temp->next = NULL;
	temp->data = data;
	if (IsEmpty()) // 비었으면
	{
		front = temp;
		rear = temp;
	}
	else // 아니면
	{
		rear->next = temp; // 지금 rear가 나의 주소를 가르키게
		rear = temp; // rear를 지금 생성한 나로 바꿈
	}
	qCount++; // 큐 사이즈 증가
}

 

 

큐의 삭제

int DeQueue()
{
	if (IsEmpty()) return NULL; // DeQueue 할게 없으면 return

	NODE* p = front; // 지금 맨 앞에 있는 노드
	int rData = p->data; // 반환할 데이터 가져오고
	front = front->next; // front를 맨 앞이 가르키고 있던 노드로 바꾸고
	delete p; // 맨 앞인 나를 지워주고
	qCount--; // 큐 사이즈 감소
	return rData;
}

 

 

[List (리스트)]

#include <iostream>
#include <list> // 헤더 가져오기
using namespace std;

int main()
{
	// list 선언
	list<int> l1;
	list<int> l2(5, 3); // 5개의 원소를 3으로 초기화
	list<int> l3{ 2,4 }; // 2, 4로 초기화

	// 값 추가
	l3.push_front(1); // 리스트의 맨 앞에 값 추가
	l3.push_back(1); // 리스트의 맺 끝에 값 추가

	// 반복자가 첫번째 값을 가리킴
	list<int>::iterator iter = l3.begin(); 
	iter++; // 두번째 값 가리킴
	iter++; // 세번째 값 가리킴

	l3.insert(iter, 3); // 반복자가 가리키는 곳에 값 추가

	// 값 삭제
	l3.pop_front(); // 리스트 맨 앞 삭제
	l3.pop_back(); // 리스트 맨 뒤 삭제

	cout << l3.size() << endl; // 리스트에 들어 있는 원소 개수 반환
	cout << l3.empty() << endl; // 리스트가 비어있으면 1, 아니면 0 반환
	
	l3.erase(iter); // 반복자가 가리키는 곳을 제거하고 그 다음 원소의 위치를 반환
}