연결리스트
- 연결리스트란?
- 노드라고 불리는 개체들이 포인터를 사용해 서로 연결된 자료구조
- 배열과 다르게 연속된 메모리 공간을 사용하지 않으며, 동적으로 크기 조절 가능
- 종류
- 단일 연결리스트
- 한 방향으로 연결된 연결리스트
- 각 노드는 다음 노드를 가르키지만, 이전 노드를 가르키는 포인터 없음
- 마지막 노드의 next 가 nullptr
- 삽입/삭제의 시간 복잡도는 O(1)(앞)/O(N)(중간)
- 검색, 접근의 시간 복잡도는 O(N)
- 이중 연결리스트
- 양방향으로 연결된 리스트
- 각 노드는 next와 prev를 가짐
- 삽입/삭제의 시간 복잡도는 O(1)
- 검색, 접근의 시간 복잡도 O(N)
- 장점
- 앞뒤로 이동이 가능해 탐색 속도가 빠름
- 노드 삭제시, 앞 뒤 노드를 몰라도 가능
- 단점
- prev 포인터를 유지해야해 메모리 사용량 증가
- 삽입/삭제시 포인터를 2개씩 조작해야해 복잡도 증가
- 원형 연결리스트
- 마지막 노드가 첫번째 노드를 가리켜 순환하는 구조
- 장점
- 끝에서 다시 처음으로 돌아갈 수 있어 순환하는 작업에 유리
- 특정 노드에서 출발하면 모든 노드 방문 가능
- 단점
- 끝이 어디인지 구분 어려움
- 무한 루프에 빠질 위험 있음
배열과 연결 리스트
- 가변 배열(vector)
- 연속된 메모리 공간 사용
- 저장 공간이 부족하면 메모리를 새로 잡아 사용하면서 저장하는데, 이때 남는 메모리가 존재하므로 메모리 단편화 일어남
- 메모리 단편화란?
- 메모리에 빈 공간 또는 자료가 여러개의 조각으로 나뉘는 현상
- 실제 공간이 남아있어도 할당이 불가능한 상태
- 삽입 삭제가 느리기 때문에 삽입 삭제가 빈번할 때 비효율적
- 주소가 연속되어 있고, index로 접근하기 때문에 검색이 빠름
- ex)
- 게임에서 몬스터는 생성 및 삭제가 빈번하지만 기획적으로 수가 변경될 수 있기 때문에 원하는 만큼 몬스터를 배열로 만든 뒤, 죽거나 필요 없어지면 안보이도록 처리, 다시 생성되야할 땐 hp등 내부의 값을 변경한 뒤 생성될 위치로 옮겨 보이도록 처리
- 메모리 풀링을 이용한 방식임
- 메모리 풀링 : 메모리를 미리 할당해두고 가져다 쓰는 방법으로 메모라 단편화를 막음
- 할당해 놓은채 사용하지 않는 메모리 발생시 메모리 누수 발생
- 메모리 할당, 해제가 빈번한 곳에서 사용
- list
- 메모리 단편화가 발생할 소지가 적음
- 메모리 단편화가 발생해도 용량이 적음
- 삽입 삭제가 빠름
- 주소를 타고 들어가야해서 검색이 느림
- 배열과 연결리스트 차이
| |
연결리스트 |
배열 |
| 메모리 구조 |
비연속적(포인터로 연결) |
연속적(배열과 동일) |
| 메모리 할당 |
동적할당(노드 단위) |
동적 할당(배열 단위, 연속적) |
| 랜덤 접근 |
불가능 |
가능 |
| 시간 복잡도 |
O(N) |
O(1) |
| 삽입/삭제(중간) |
O(1)(포인터 변경) |
O(N)(밀어야함) |
| 삽입/삭제(끝) |
O(1) |
O(1)(여유공간 있을 때), O(N)(리사이징 발생시) |
| 메모리 오버헤드 |
높음(포인터 추가 필요) |
낮음(데이터만 저장) |
| 캐시 효율성 |
낮음(노드 흩어짐) |
높음(연속된 메모리) |
| 배열 크기 조절 |
추가/삭제시 새로운 노드 할당 |
크기 초과 시 재할당 & 복사 필요 |
단일 연결 리스트 구현
#pragma once
#include<iostream>
template<typename T>
class LinkedList
{
public:
struct Node;//전방선언
public:
LinkedList(Node* head)
{
this->head = head;
}
static Node* Create(T data)
{
Node* node = new Node();
node->Data = data;
node->Next = nullptr;
return node;
}
static void Destroy(Node* node)
{
delete node;
node = nullptr;
}
Node* Head(){return head;}
void Push(Node* node)
{
Node* tail = head;
while(tail->Next != nullptr)
tail = tail->Next;
tail->Next = node;
}
void Insert(Node* current, Node* node)
{
node->Next = current->Next;
current->Next = node;
}
void Insert(int index, Node* node)
{
Node* temp = GetNode(index);
Insert(temp, node);
}
Node* GetNode(int index)
{
Node* curr = head;
while (curr != nullptr && --index >= 0)
curr = curr->Next;
return curr;
}
int GetNodeCount()
{
int count = 0;
Node* current = head;
while (current != nullptr)
{
current = current->Next;
count++;
}
return count;
}
void Print(Node* node = nullptr)
{
if(node == nullptr)
return;
std::cout<<node->Data <<std::endl;
Print(node->Next);
}
public:
struct Node
{
T Data;
Node* Next;
};
private:
Node* head;
};
