Linked List
특징
- 물리적으로는 메모리 공간에 흩어져 있는 데이터를 집합적으로 연결하는 것
- 배열은 물리적으로 연속된 공간에 데이터가 위치하지만 Linked List는 떨어져 있지만 포인터를 통해 연결
- 생성시 크기를 정해야 하는 배열과 달리 동적으로 공간이 늘어나고 줄일 수 있음
- 각각의 노드는 값을 저장하는 데이터 파트와 앞선 노드들과의 연결을 괸리하는 링크 파트로 구성됨
- 기존의 Stack, Queue뿐만 아니라 Tree, Graph 등의 자료구조에 다양하게 사용할 수 있음
- 첫번째 노드부터 순서대로 연결되어 있으므로 특정 노드를 찾을 때 앞에서부터 연쇄적으로 접근해 찾을 수 있음
장점
- 고정되지 않아 동적으로 크기를 바꿀 수 있음
- 특정 위치에 삽입할 때 기존 배열은 해당 위치보다 뒤에 있는 것들을 전부 뒤로 밀고 삽입해야하나 그저 포인터의 지시 대상을 바꾸는 것으로 효율적이게 수행 가능
- 삭제하는 것 또한 동일하게 배열 내 요소들의 이동 없이 지시 대상을 바꾸는 것으로 실행 가능
- 필요할 때 메모리를 동적으로 할당해 공간을 확보하므로 미리 큰 공간을 확보해 둬야하는 배열보다 유리
단점
- 배열보다 복잡해 오류의 가능성이 높고 포인터를 잘 관리하지 못했을 때 문제가 발생
- 실제 저장할 데이터 외에도 포인터 등 노드의 연결을 관리할 요소가 필요해 메모리 공간을 더 요구함
- 순회, 삽입, 삭제가 일반 배열보다는 복잡함
- 자주 동적 할당이 이루어져 프로그램 속도를 늦출 수 있음
구성 요소
노드
- Data Field와 Link Field로 구성됨
- Data Field : 실제 데이터를 저장
- Link Field : 다음 노드의 주소를 저장. 해당 요소를 통해 노드들이 연결됨
Head Pointer
- 향후 다른 노드에 접근하기 위한 시작 지점
- 마지막 노드의 Link Field의 포인터를
NULL값으로 설정됨
종류
Singly Linked List
- 노드들이 오직 한 방향으로만 연결됨
- 마지막 노드는
NULL값을 지시함
Circular Linked List
- 한 방향으로 진행하는 것은 Singly Linked List와 동일
- 마지막 노드는 첫번째 노드를 지시해 순환하는 구조를 가짐
Doubly Linked List
- 각각의 노드들은 2개의 Limk Field를 가져 자신의 앞에 있는 데이터와 뒤에 있는 데이터 모두를 저장
- 양방향 순회가 가능
구성 요소
Node 클래스
data : 실제 값을 저장할 변수
next : 다음 노드의 포인터를 저장할 변수
LinkedList 클래스
headPointer : Linked List의 시작지점이 될 포인터
Add(T data) : 새로운 값을 Linked List에 추가
Insert(int index, T data) : index지점에 data를 추가
Delete(int index) : index지점의 요소를 제거
Clear() : Linked List내의 모든 요소를 제거
"LinkedList name"[int index] : index를 통해 해당 요소에 접근
구현
template <typename T>
class Node
{
public:
Node(T value, Node *ptr) { data = value; next = ptr; }
T data;
Node *next;
};
template <typename T>
class LinkedList
{
private:
Node<T> *head;
public:
LinkedList() : head(nullptr) {}
void Add(T data)
{
Node<T> *newNode = new Node<T>(data, nullptr);
if (!head)
{
head = newNode;
}
else
{
Node<T> *temp = head;
while (temp->next)
{
temp = temp->next;
}
temp->next = newNode;
}
}
void Insert(int index, T data)
{
Node<T> *newNode = new Node<T>(data, nullptr);
if (index == 0)
{
newNode->next = head;
head = newNode;
return;
}
Node<T> *temp = head;
for (int i = 0; i < index - 1 && temp; i++)
{
temp = temp->next;
}
if (temp)
{
newNode->next = temp->next;
temp->next = newNode;
}
else
{
throw "Index out of bounds";
}
}
void RemoveAt(int index)
{
if (!head)
{
throw "List is empty";
}
if (index == 0)
{
Node<T> *temp = head;
head = head->next;
delete temp;
return;
}
Node<T> *temp = head;
for (int i = 0; i < index - 1 && temp; i++)
{
temp = temp->next;
}
if (temp && temp->next)
{
Node<T> *toDelete = temp->next;
temp->next = toDelete->next;
delete toDelete;
}
else
{
throw "Index out of bounds";
}
}
T operator[](int index)
{
Node<T> *temp = head;
for (int i = 0; i < index && temp; i++)
{
temp = temp->next;
}
if (temp)
{
return temp->data;
}
else
{
throw "Index out of bounds";
}
}
void Clear()
{
Node<T> *temp = head;
while (temp)
{
Node<T> *toDelete = temp;
temp = temp->next;
delete toDelete;
}
head = nullptr;
}
};Node 클래스
template <typename T>
class Node
{
public:
Node(T value, Node *ptr) { data = value; next = ptr; }
T data;
Node *next;
};- 노드의 기본 구성대로 Data Field와 Link Field로 구성되어 생성자에서 포인터와 저장할 데이터를 입력받록 함
Linked List 클래스
Private 필드
private:
Node<T> *head;- Private 하게 저장해야할 부분은 시작 지점이 될
head포인터만 존재
생성자
LinkedList() : head(nullptr) {}- 생성시
head를null포인터를 생성해 연결
Add(T date) & Insert(int index, T data)
void Add(T data)
{
Node<T> *newNode = new Node<T>(data, nullptr);
if (!head)
{
head = newNode;
}
else
{
Node<T> *temp = head;
while (temp->next)
{
temp = temp->next;
}
temp->next = newNode;
}
}- 리스트의 가장 마지막에 값을 추가하는 함수
- 새로운 노드를
newNode로 생성하면서 메모리를 동적 할당 - 만약
head가 비어있다면head에 새로운 노드를 연결하는 것으로 완료 - 만약
head가 비어있지 않다면next노드가 비어있는 것을 찾아 해당 노드의next에 새로운 노드를 연결
void Insert(int index, T data)
{
Node<T> *newNode = new Node<T>(data, nullptr);
if (index == 0)
{
newNode->next = head;
head = newNode;
return;
}
Node<T> *temp = head;
for (int i = 0; i < index - 1 && temp; i++)
{
temp = temp->next;
}
if (temp)
{
newNode->next = temp->next;
temp->next = newNode;
}
else
{
throw "Index out of bounds";
}
}Add함수와 비슷하게 작동하나 특정 인덱스 위치에 값을 추가
for (int i = 0; i < index - 1 && temp; i++)
{
temp = temp->next;
}head에서 시작해 선택한 인덱스 지점까지 이동해 해당 위치의 포인터가null인지 확인 하고 그렇지 않다면 해당 노드의next를 추가하고자 하는 노드의next로 연결하고,temp노드의next를 새로 추가하는 노드로 설정
RemoveAt(int index)
void RemoveAt(int index)
{
if (!head)
{
throw "List is empty";
}
if (index == 0)
{
Node<T> *temp = head;
head = head->next;
delete temp;
return;
}
Node<T> *temp = head;
for (int i = 0; i < index - 1 && temp; i++)
{
temp = temp->next;
}
if (temp && temp->next)
{
Node<T> *toDelete = temp->next;
temp->next = toDelete->next;
delete toDelete;
}
else
{
throw "Index out of bounds";
}
}- 입력받은 인덱스 위치
index에 있는 값을 삭제하기 위해Insert함수와 같이 해당 노드까지 순차적으로 이동을 실시 - 현재 있는 노드의 다음 노드를 삭제하기 위해 현재 노드의 다음 노드를 삭제하고자 하는 노드의 다음 노드로 연결하여 삭제하고자 하는 노드를 건너뛰도록 하고 삭제를 진행
Operator
T operator[](int index)
{
Node<T> *temp = head;
for (int i = 0; i < index && temp; i++)
{
temp = temp->next;
}
if (temp)
{
return temp->data;
}
else
{
throw "Index out of bounds";
}
}- 배열에서
arr[2]와 같이 접근하는 것을 구현하기 위해operator[]를 선언해 구현 Insert,RemoveAt함수와 유사하게 특정 인덱스까지 이동하고 해당 위치의 값을 반환
