2022. 6. 27. 20:06ㆍ코딩 1막 <C++개념편>
1. 링크드리스트의 개념
// 연결 리스트 //
// 앞의 세 구조와 달리 메모리에 있는 데이터의 물리적배치를 사용하지 않는 데이터구조다.
// index나 위치보다 '참조 시스템'을 사용한다.
// 각 요소는 '노드'라는 것에 저장되며, 다음 노드연결에 대한 포인터 또는 주소가 포함된 또 다른 노드에 저장한다.
// 모든 노드가 연결된 때까지 반복이 돼서 노드의 연결로 이루어진 자료구조다.
// 장점 : 새로운 요소의 추가와 삭제가 용이하다. 메모리를 더 효율적으로 쓸 수 있어 대용량 데이터 처리에 적합하다.
// 단점 : 배열보다 메모리를 더 사용한다. 처음부터 끝까지 순회하기 때문에 원하는 값을 비효율적으로 처리한다.
// 사용예시) 음악 플레이어, 이미지 뷰어, 갤러리, 데이터를 연속적으로 빠르게 삽입 및 제거가 필요할 때
// 벡터외 연결리스트의 차이점은 '백터는 중간삽입시 원소를 밀어내지만, 리스트는 노드를 연결만 하기때문에 삽입 및 삭제 부분에서 시간복잡도의 우위를 가진다'입니다.
2. 링크드리스트과 벡터의 차이
리스트는 외부에서 보면 벡터와 완전히 동일하다. 벡터는 동적배열이므로 새 공간이 할당되고 데이터를 추가할때 추가하고 싶은 값 다음의 데이터들이 한칸씩 뒤로 옮겨지므로 연산이 많아져서 비효율적이다. 하지만 리스트는 노드만 연결하기때문에 벡터보다 시간복잡도면에서 우위를 갖는다.
***추가나 삭제가 빈번히 이루어질 대용량의 자료구조를 갖을때는 배열(arrayed list)보다 링크드리스트(Linked list)를 사용해야한다. 예시로 인벤토리를 구현할때는 인벤토리 내 개수가 한정적으로 딱 정해져있을땐 배열을 쓰는게 낫지만, 일반적인 경우의 인벤토리를 구현할때는 링크드리스트를 쓰는게 낫다.
3. 링크드리스트 만들기
(1) 노드 생성
#include <iostream>
using namespace std;
class Node
{
public:
int value;
Node* next = nullptr;
};
(2) 링크드리스트 선언부
- 큐와 스택과는 다르게 연결리스트는 노드들끼리 연결되어 있어 수많은 원소들 사이에 새로운 값을 추가하거나 삭제할 수 있는 기능이 존재한다.
- 코드의 가독성과 성능을 증대시키기 위해 Node* At라는 해당 위치의 노드를 반환하는 함수를 추가한다!!
class LinkedList
{
private:
Node* head = nullptr;
Node* tail = nullptr;
int size = 0;
public:
void AddNode(int _value); // 맨뒤에 추가
void AddNode(int _value, int position); // position위치에 추가
void RemoveNode(int position); // position위치에 삭제
int SerchValue(int value); // value를 찾아 position반환
void Show(); // 전체 출력
int GetSize(); // size게터
bool IsEmpty(); // 비어있는지 확인
~LinkedList(); // 클래스소멸자
Node* At(int position); // 해당 위치의 노드를 반환
};
(3) Add함수
- 큐와 스택의 Add함수와 동일한 기능을 갖기때문에 구현하는 방식도 동일하다.
void LinkedList::AddNode(int _value)
{
Node* newNode = new Node();
newNode->value = _value;
size++;
if (IsEmpty())
{
head = newNode;
tail = newNode;
}
else
{
tail->next = newNode;
tail = newNode;
}
};
(4) Add(int value, int position)함수
- 추가하고자 하는 원하는 값(value)을 원하는 위치(position)에 넣기 위한 함수이다.
- Node* At()라는 해당 위치의 노드를 반환하는 함수를 선언하여 추가하고자 하는 위치의 전 노드에 접근이 용이해진다.
void LinkedList::AddNode(int _value, int position)
{
if (position > size)
{
AddNode(_value);
return;
}
Node* newNode = new Node();
newNode->value = _value;
size++;
Node* prevlnsertPos = At(position - 1);
newNode->next = prevlnsertPos->next;
prevlnsertPos->next = newNode;
};
(5) remove()함수
- 코드구현의 접근방식은 다음 그림과 같다.
~~~우리는 C를 지우고 싶다~~~
①prevRemovePtr는 처음에 head로부터 우리가 지우길 원하는 위치(그림상에서는 B)까지 이동해야한다
②removePtr = prevRemovePtr->next; C를 지울꺼니까 B의 다음 위치를 저장
③delete removePtr; 저장해둔 C를 지운다.
void LinkedList::RemoveNode(int position)
{
Node* prevRemovePtr;
Node* removePtr;
prevRemovePtr = At(position - 1);
removePtr = prevRemovePtr->next;
prevRemovePtr->next = removePtr->next; // B가 D를 가리킨다
delete removePtr;
};
(6) Node* At(int position) : 해당 위치의 노드를 반환하는 함수
- 링크드리스트의 구현을 위해 매우 유용한 개념이다!!
Node* LinkedList::At(int position) // 해당 위치의 노드를 반환
{
if (position <= 0)
{
return head;
}
else if (position >= size)
{
return tail;
}
else
{
Node* current = head;
for (int i = 0; i < position; i++)
{
current = current->next;
}
return current;
}
}
(7) int SerchValue(int value)
- 값(value)를 입력받아 위치(position)를 반환하는 함수
int LinkedList::SerchValue(int value)
{
int position = 0;
Node* current = head;
for (int i = 0; i < size; i++)
{
if (value == current->value) { position = i; break; }
else { position = -2147483647; }
current = current->next;
}
return position;
};
(8) void Show(), int GetSize(), bool IsEmpty()
- 큐와 스택에서도 등장했던 함수들
- 노드 전체를 출력하는 함수인 Show(), 사이즈를 반환하는 게터함수인 GetSize(), 빈공간을 확인하는 IsEmpty().
void LinkedList::Show()
{
Node* current = head;
while (current != nullptr)
{
cout << current->value << endl;
current = current->next;
}
};
int LinkedList::GetSize()
{
return size;
};
bool LinkedList::IsEmpty()
{
if (head == nullptr)
{
return true;
}
else
{
return false;
}
};
LinkedList::~LinkedList()
{
Node* current = head;
Node* temp;
while (current != nullptr)
{
temp = current;
current = current->next;
delete temp;
}
delete current;
}
(9) main
void main()
{
LinkedList intLinkedList;
intLinkedList.AddNode(10);
intLinkedList.AddNode(20);
intLinkedList.AddNode(30);
intLinkedList.AddNode(40);
intLinkedList.AddNode(80, 2);
intLinkedList.AddNode(100, 200);
// intLinkedList.RemoveNode(2);
// 0 1 2 3 중 i의 위치의 노드를 가져오는 함수(반복문이므로 전체출력)
for (int i = 0; i < intLinkedList.GetSize(); i++)
{
cout << intLinkedList.At(i)->value << endl;
}
}
'코딩 1막 <C++개념편>' 카테고리의 다른 글
[C++] 38. namespace (0) | 2022.06.27 |
---|---|
[C++] 37. 상수화 (0) | 2022.06.27 |
[C++] 35. 자료구조 : 큐와 스택(Queue & Stack) (0) | 2022.06.23 |
[C++] 34. 게터와 세터 (0) | 2022.06.22 |
[C++] 33. 클래스 (0) | 2022.06.22 |