Linked List : 연결 리스트
- 특징
1) 노드와 포인터로 이루어진 선형 자료구조
2) 노드는 데이터와 다음 노드를 가리키는 포인터로 구성된다
3) 크기가 가변적이므로 동적 메모리 할당과 함께 사용되기도 한다
- 장점
1) 삽입, 삭제가 용이하며, 데이터의 크기가 가변적일 경우 유용하다
2) 데이터를 읽는 것보다 데이터를 추가, 삭제하는게 빠르다
- 단점
1) 데이터를 찾는 데 걸리는 시간이 선형적으로 증가하기 때문에 탐색 속도가 느리다
2) 중간에 있는 노드를 삭제하면 메모리 낭비가 발생할 수 있다
Linked List.h
#pragma once
void DoLinkedList();
void PrintList();
class LLN // Linked List Node
{
public:
static LLN* Create(DataType data);
static void Insert(LLN* cur, LLN* newNode);
void InsertHead();
void Push();
void Remove();
static void RemoveAll();
static LLN* GetNode(int index);
const DataType GetData() { return Data; }
static const int GetLength() { return Length; }
static int GetNodeCount(int index);
static const LLN* GetHead() { return Head; }
static const LLN* GetTail() { return Tail; }
private:
static void RemoveAll(const LLN* head);
private:
DataType Data;
LLN* Next;
static int Length;
static LLN* Head;
static LLN* Tail;
};Linked List.cpp
#include "../../stdafx.h"
#include "LinkedList.h"
int LLN::Length = 0;
LLN* LLN::Head = nullptr;
LLN* LLN::Tail = nullptr;
void DoLinkedList()
{
LLN* node = nullptr;
LLN::Create(232)->Push();
for (int i = 0; i < 5; i++)
{
node = LLN::Create(i);
node->Push();
}
PrintList();
cout << endl;
cout << "-------------------------------------------------" << endll;
// 중간에 값 삽입, 맨 앞에 값 삽입
LLN* newNode = LLN::Create(200);
LLN::Insert(LLN::GetNode(2), newNode);
LLN* forwordNode = LLN::Create(123123);
forwordNode->InsertHead();
PrintList();
cout << endl;
cout << "-------------------------------------------------" << endll;
// 특정 인덱스부터 출력
int count = LLN::GetNodeCount(1);
cout << "index[1] ~ Tail Length : " << count << endl;
cout << endl;
cout << "-------------------------------------------------" << endll;
LLN::GetNode(3)->Remove();
PrintList();
cout << endl;
cout << "-------------------------------------------------" << endll;
LLN::RemoveAll();
PrintList();
Pause;
}
void PrintList()
{
if (LLN::GetLength() <= 0)
cout << "List Is Null" << endl;
for (int i = 0; i < LLN::GetLength(); i++)
cout << "index [ " << i << " ] " << LLN::GetNode(i)->GetData() << endl;
}
LLN* LLN::Create(DataType data)
{
LLN* node = new LLN();
node->Data = data;
node->Next = nullptr;
return node;
}
void LLN::Insert(LLN* cur, LLN* newNode) // cur 다음 인덱스에 들어옴
{
newNode->Next = cur->Next;
cur->Next = newNode;
++Length;
}
void LLN::InsertHead()
{
this->Next = Head; // 새로운 노드가 (전)머리의 포인터를 가리키게 함
Head = this; // 새로운 노드를 머리 포인터로 설정
++Length;
}
void LLN::Push()
{
if (Head == nullptr) // 리스트에 노드가 존재하지 않으면
{
Head = this;
Tail = this;
}
else
{
Tail->Next = this;
Tail = this;
}
++Length;
}
void LLN::Remove()
{
if (this == Head)
{
if (this->Next)
Head = this->Next;
delete this;
return;
}
LLN* checker = Head;
while (1)
{
if (checker->Next == this)
{
checker->Next = this->Next;
delete this;
break;
}
else
checker = checker->Next;
}
--Length;
}
void LLN::RemoveAll()
{
Length = Length <= 0 ? 0 : --Length;
if (Head == nullptr)
{
cout << "List is already NULL" << endl;
return;
}
if (Head->Next != nullptr)
RemoveAll(Head->Next);
cout << Head->Data << "\tData Remove Completed!" << endl;
delete Head;
Head = nullptr;
Tail = nullptr;
}
LLN* LLN::GetNode(int index)
{
if (Head == nullptr)
return nullptr;
LLN* find = Head;
while (find != nullptr && --index >= 0)
find = find->Next;
return find;
}
int LLN::GetNodeCount(int index)
{
LLN* cur = GetNode(index);
if (cur == nullptr)
return -1;
int count = 1;
while (cur->Next != nullptr)
{
cur = cur->Next;
++count;
}
return count;
}
void LLN::RemoveAll(const LLN* head)
{
// 재귀함수가 실행된다 == 길이가 하나 줄어든다
--Length;
// 현재 노드의 노드의 다음 노드가 비어있지 않으면
if (head->Next != nullptr)
// 재귀함수로 다음 노드를 현재 노드로 넣어서 다시 실행
RemoveAll(head->Next);
// 다음 노드가 nullptr일 경우에만 실행
cout << head->Data << "\tData Remove Completed!" << endl;
delete head;
}DoubleLinkedList.h
#pragma once
void DoDoubleLinekdList();
class DLLN
{
public:
static DLLN* Create(DataType data);
static void Insert(DLLN* cur, DLLN* newNode);
static void InsertHead(DLLN* newNode);
static void Push(DLLN* newNode);
void Remove();
static void RemoveAll(const DLLN* head);
static void SetHead(DLLN* node);
static void SetTail(DLLN* node);
static const DLLN* GetHead() { return Head; }
static const DLLN* GetTail() { return Tail; }
void SetNext(DLLN* next) { Next = next; }
void SetPrev(DLLN* prev) { Prev = prev; }
void SetData(DataType data) { Data = data; }
const DLLN* GetNext() { return Next; }
const DLLN* GetPrev() { return Prev; }
const DataType GetData() { return Data; }
static DLLN* GetNode(int index);
static const int GetLength() { return Length; }
static int GetNodeCount(int index);
static int GetNodeReverseCount(int index);
private:
DLLN* Prev;
DLLN* Next;
DataType Data;
static int Length;
static DLLN* Head;
static DLLN* Tail;
};DoubleLinkedList.cpp
#include "../../stdafx.h"
#include "DoubleLinkedList.h"
DLLN* DLLN::Head = nullptr;
DLLN* DLLN::Tail = nullptr;
int DLLN::Length = 0;
DLLN* DLLN::Create(DataType data)
{
DLLN* node = new DLLN();
node->SetNext(NULL);
node->SetPrev(NULL);
node->SetData(data);
return node;
}
void DLLN::Insert(DLLN* cur, DLLN* newNode)
{
if (cur == Tail)
{
Push(newNode);
return;
}
newNode->Prev = cur;
newNode->Next = cur->Next;
cur->Next->Prev = newNode;
cur->Next = newNode;
++Length;
}
void DLLN::InsertHead(DLLN* newNode)
{
Head->Prev = newNode;
newNode->Next = Head;
Head = newNode;
++Length;
}
void DLLN::Push(DLLN* newNode)
{
if (Head == nullptr)
{
Head = newNode;
Tail = newNode;
}
else
{
Tail->Next = newNode;
newNode->Prev = Tail;
Tail = newNode;
}
++Length;
}
void DLLN::Remove()
{
if (Head == Tail)
{
delete this;
return;
}
if (this == Head)
{
Head->Next->Prev = nullptr;
Head = Head->Next;
}
else if (this == Tail)
{
Tail->Prev->Next = nullptr;
Tail = Tail->Prev;
}
else
{
this->Prev->Next = this->Next;
this->Next->Prev = this->Prev;
}
--Length;
delete this;
}
void DLLN::RemoveAll(const DLLN* head)
{
if (head == nullptr)
{
cout << "Empty" << endl;
return;
}
if (head->Next != nullptr)
RemoveAll(head->Next);
delete head;
Length = 0;
return;
}
void DLLN::SetHead(DLLN* node)
{
Head->Prev = node;
node->Next = Head;
Head = node;
}
void DLLN::SetTail(DLLN* node)
{
Tail->Next = node;
node->Prev = Tail;
Tail = node;
}
DLLN* DLLN::GetNode(int index)
{
if (index >= Length || index < 0)
{
cout << "Out of range" << endl;
return nullptr;
}
DLLN* find = Head;
while (find != nullptr && --index >= 0)
find = find->Next;
return find;
}
int DLLN::GetNodeCount(int index)
{
DLLN* cur = GetNode(index);
if (cur == nullptr)
return 0;
int count = 0;
while (cur->Next != nullptr)
{
cur = cur->Next;
++count;
}
return count;
}
int DLLN::GetNodeReverseCount(int index)
{
DLLN* cur = GetNode(index);
if (cur == nullptr)
return 0;
int count = 1;
while (cur->Prev != nullptr)
{
cur = cur->Prev;
++count;
}
return count;
}
void DoDoubleLinekdList()
{
DLLN* node = nullptr;
for (int i = 0; i < 5; i++)
{
node = DLLN::Create(i);
DLLN::Push(node);
}
for (int i = 0; i < DLLN::GetLength(); i++)
cout << "index [ " << i << " ] " << DLLN::GetNode(i)->GetData() << endl;
cout << "----------------------------------------------" << endl;
DLLN* newNode = DLLN::Create(2151);
DLLN::Insert(DLLN::GetNode(2), newNode);
DLLN* headNode = DLLN::Create(323);
DLLN::InsertHead(headNode);
for (int i = 0; i < DLLN::GetLength(); i++)
cout << "index [ " << i << " ] " << DLLN::GetNode(i)->GetData() << endl;
cout << "----------------------------------------------" << endl;
DLLN::GetNode(4)->Remove();
for (int i = 0; i < DLLN::GetLength(); i++)
cout << "index [ " << i << " ] " << DLLN::GetNode(i)->GetData() << endl;
cout << "----------------------------------------------" << endl;
int count = DLLN::GetNodeReverseCount(DLLN::GetLength() - 1);
for(int i = count - 1; i >= 0; i--)
cout << "index [ " << i << " ] " << DLLN::GetNode(i)->GetData() << endl;
DLLN::RemoveAll(DLLN::GetHead());
Pause;
}'자료구조' 카테고리의 다른 글
| [C++/자료구조] 힙(Heap) (0) | 2023.07.15 |
|---|---|
| [자료구조] 자료구조별 게임의 기능 구현 예시 (0) | 2023.07.14 |
| [C++/자료구조] 이진트리(Binary Tree) (0) | 2023.07.08 |
| [C++/자료구조] 큐(Queue) (0) | 2023.07.08 |
| [C++/자료구조] 스택(Linked List) (0) | 2023.07.08 |
댓글