<C++> 12. 리스트

리스트

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

연결리스트

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

배열 vs 연결리스트

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

연결리스트로 스택 구현하기

 

스택의 삽입

스택 삽입 구현하기

void Push(int _data)
{
	NODE* temp = new NODE;
	temp->next = NULL;
	temp->data = _data;
	if (isEmpty())
	{
		s_Top = temp;
	}
	else
	{
		temp->next = temp;
        s_Top = temp;
	}
}

스택의 삭제

 

스택 삭제 구현하기

int Pop()
{
	if (isEmpty()) return -1;
	NODE* delTemp = s_Top;
	int rData = delTemp->data;
	s_Top = delTemp->next;
	delete(delTemp);
	return rData;
}

큐의 삽입

큐 삽입 구현하기

void enQueue(int _data)
{
	NODE* temp = new NODE;
	temp->next = NULL;
	temp->data = _data;
	if (isEmpty()) {
		q_front = temp;
		q_rear = temp;
	}
	else {
		q_front = temp;
		q_rear = temp->next;
	}
	q_count++;
}

 

큐 삭제 구현하기

int deQueue()
{
	if (isEmpty()) {
		cout << "\nQueue is Empty\n\n";
		return -1;
	}
	NODE* delTemp = q_front;
	int rData = delTemp->data;
	q_rear = delTemp->next;
	delete(delTemp);
	q_count--;
	return rData;
}

STL 리스트 사용법