연결 리스트/Linked list

연결 리스트란?

연결 리스트란 쉽게 말해 원소를 저장할 때, 그 다음 원소의 위치를 같이 저장하는 선형 자료구조이며, 이때 원소들은 붙어있지 않고 흩어져있다. 연결 리스트를 사용했을때의 주요 시간 복잡도는 다음과 같다.

1. k번째 원소를 확인/변경하기 위해서는 O(k)가 필요함
   => 해당 연산을 반복 수행해야하는 경우, 연결 리스트보다 배열이 효율적(배열은 O(1))
2. 임의의 위치에 원소를 추가/제거는 O(1)이 필요함
   => 해당 연산을 반복 수행해야하는 경우, 배열보다 연결 리스트가 효율적(배열은 O(N))

 

연결 리스트의 종류는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 있다.

• 단일 연결 리스트 - 각 원소가 자신의 다음 원소 주소를 들고 있는 구조
• 이중 연결 리스트 - 각 원소가 자신의 이전, 다음 원소 주소를 들고 있는 구조
                               c++에서 제공하는 STL에 있는 연결리스트는 이중 연결 리스트 구조이다.
• 원형 연결 리스트 - 단일 연결 리스트/ 이중 연결 리스트 구조에서 끝이 처음과 연결되어있는 구조

---

정석적인 구현 방식(이중 연결 리스트)

struct NODE{
    NODE* next;
    NODE* prev;
    int data
}

Node* head;	//더미 머리 
Node* tail;	//더미 꼬리 
int size;	//링크드 리스트 크기

// 리스트 초기화
void InitList()
{
	//머리 메모리 할당
    head = (Node*)malloc(sizeof(Node));	
    //꼬리 메모리 할당
	tail = (Node*)malloc(sizeof(Node));	
    	head->prev = head;	
	head->next = tail;			
   	tail->prev = head;			
	tail->next = tail;		
	size = 0;				
}

//특정 노드 뒤에 삽입
bool InsertAfter(int value, Node* node)
{
	if (node == tail)			
		return false;

	Node* newNode = (Node*)malloc(sizeof(Node));	
	newNode->data = value;				
	newNode->next = node->next;			
    	newNode->prev = node;				
    	node->next = newNode;			
        node->next->prev = newNode;		
	size++;						
	return true;
}

//특정 노드 앞에 삽입
bool InsertBefore(int value, Node* node)
{
	if (node == head)				
		return false;

	Node* newNode = (Node*)malloc(sizeof(Node));	
	newNode->data = value;				
	newNode->prev = node->prev;
	newNode->next = node;
    	node->prev->next = newNode;			
	node->prev = newNode;
	size++;
	return true;   
}

//특정 노드 삭제
bool DeleteNode(Node* node)
{
	if (node == head || node == tail)		
		return false;

	node->next->prev = node->prev;		
	node->prev->next = node->next;		
	printf("delete %d\n", node->data);
	free(node);					//메모리 해제
	size--;
	return true;
}

//값을 이용해 노드 검색
Node* FindNodeUsingValue(int value)
{
	Node* temp = head->next;		
	while (temp != tail)			
	{
		if (temp->data == value)	
		{
			printf("Find Value Data : %d \n", temp->data);
			return temp;		
		}
		temp = temp->next;		
	}
	return temp;				
}

//인덱스를 이용해 노드 검색
Node* FindNodeUsingIndex(int num)
{
	if (num < 0 || num >= size)			
		return tail;

	Node* temp = head->next;		
	for (int i = 0; i < num;++i)	
		temp = temp->next;			

	printf("Find index : %d Data : %d \n", num, temp->data);
	return temp;
}

 

---

STL을 활용한 구현 방식(이중 연결 리스트)

list의 사용법에 알기전에 우선 iterator에 대해 간단히 정리해보자. iterator란 라이브러리의 방식대로 자료구조를 액세스 할 수 있게 해주는 반복자이다. 즉 컨테이너에 저장되어 있는 모든 원소들을 전체적으로 훑어 나갈 때 사용하는 일종의 포인터와 비슷한 객체라고 보면 된다. 알고리즘마다 다른 방식으로 컨테이너를 훑어가기 때문에, 반복자에도 여러 종류가 존재한다. list에서는 다음과 같은 반복자가 사용된다.

• begin() : beginning iterator 반환
• end() : end iterator 반환

이 외에 다른 반복자의 종류에 대해서는 담번에 알아보고 list의 기능들에 대해 마저 작성!

#include <iostream> 
#include <list> 

using namespace std; 
  
int main() 
{ 
    // 리스트 생성 
    list<int> a;  
 
    // 원소 추가 
    a.push_back(22); 
    a.push_back(33); 
    a.push_front(11); 
    a.push_back(44); 
    a.push_back(55); 
  
    // 반복자 생성 
    list<int>::iterator iter = a.begin(); 
 
    // 리스트 출력 
    for(iter=a.begin(); iter!=a.end(); iter++) 
    { 
        cout << *iter << endl; // 원본 리스트: 11 22 33 44 55 
    } 
  
    // 원소 삭제 
    a.pop_front(); 
    a.pop_back(); 
    
    // 리스트 사이즈 출력 
    cout << a.size() << endl; // 3 출력( 22, 33, 44 이므로) 
  
    // 리스트가 비어있는가 
    cout << a.empty() << endl; // 비어있지 않으므로 0 반환 
      
    // 리스트 첫번째 원소 출력 
    cout << a.front() << endl; // 22 
  
    // 리스트 마지막 원소 출력 
    cout << a.back() << endl; // 44 
  
    iter++; // 반복자가 두번째 원소(33)를 가리킴 
    iter++; // 반복자가 세번째 원소(44)를 가리킴 
    a.insert(iter, 55555); 
    for(iter=a.begin(); iter!=a.end(); iter++) 
    { 
        cout << *iter << endl; //세번째 원소 전에 추가하는 것(22,55555,33,44) 
    }  
}