더블 링크드 리스트(Double Linked List)
더블 링크드 리스트란?
- 노드를 연결해서 만든 리스트다.
- 데이터와 포인터를 이용하여 노드를 만들고 이것을 기차처럼 연결시켜준다.
- 머리(헤드)와 꼬리(테일)을 가지고있다.
- 싱글 링크드 리스트 보다 이전노드를 가지고있어야 하기때문에 메모리를 더 차지하게된다.
- 싱글리스트는 한쪽으로만 탐색이 가능하지만 더블 링크트 리스트는 양쪽에서 탐색이 가능하게 된다.
싱글 링크드 리스트 구현
- 노드 추가
- 노드 탐색
- 노드 삭제
- 노드 삽입
노드 추가
싱글 링크드 리스트의 경우 이전 노드를 알 수가 없어 노드를 추가할땐 무조건 끝까지 탐색 후 넣어줘야 했지만
더블 링크드 리스트의 경우 이전 노드를 알 수 있어 단순히 테일의 이전노드를 참조하여 간단히 추가 할 수 있다.
void LinkedList::Add(const int& NewData)
{
Node* NewNode = new Node();
if (NewNode != nullptr)
{
NewNode->Data = NewData;
}
if (Tail != nullptr)
{
NewNode->Prev = Tail->Prev;
NewNode->Next = Tail;
Tail->Prev->Next = NewNode;
Tail->Prev = NewNode;
}
}노드 탐색
테일 전까지의 노드를 순회하면서 같은 데이터를 찾아야한다.
싱글 링크트 리스트와 코드차이는 없다. 다만 뒤에서 탐색하는걸 조건에 넣어 만들면 양방향 탐색이 가능해진다.
Node* LinkedList::Search(const int& Data)
{
Node* CurrentNode = Head;
if (CurrentNode != nullptr)
{
while (CurrentNode->Next != Tail)
{
if (CurrentNode->Next->Data == Data)
{
return CurrentNode->Next;
}
CurrentNode = CurrentNode->Next;
}
std::cout << "검색 할 노드가 없습니다" << std::endl;
return nullptr;
}
else
{
std::cout << "헤드가 없습니다" << std::endl;
return nullptr;
}
}
노드 삽입
헤드의 다음노드를 첫번째 노드라고 생각하고 첫 번째 노드와 두 번째 노드사이에 새로운 노드를 넣는다.
그림에선 첫 번째 뒤에 삽입 하기 위해 1이라는 인덱스를 필요로 한다.
void LinkedList::Insert(const int& NewData, const int& Index)
{
Node* CurrentNode = Head;
if (CurrentNode != nullptr)
{
for (int i = 0; i < Index; ++i)
{
if (CurrentNode != nullptr)
{
CurrentNode = CurrentNode->Next;
}
else
{
std::cout << Index << "번째의 노드가 없습니다" << std::endl;
return;
}
}
}
if (CurrentNode == nullptr)
{
std::cout << Index << "번째의 노드가 없습니다" << std::endl;
return;
}
Node* NewNode = new Node();
if (NewNode != nullptr)
{
NewNode->Data = NewData;
CurrentNode->Next->Prev = NewNode;
NewNode->Next = CurrentNode->Next;
NewNode->Prev = CurrentNode;
CurrentNode->Next = NewNode;
}
}노드 제거
테일 전까지 노드를 순회하면서 같은 데이터를 찾고 그 데이터가 있으면 제거를 할 수 있다.
void LinkedList::Remove(Node* InRemoveNode)
{
Node* CurrentNode = Head->Next;
if (CurrentNode != nullptr && InRemoveNode != nullptr)
{
if (CurrentNode == InRemoveNode)
{
Head->Next = InRemoveNode->Next;
InRemoveNode->Next->Prev = Head;
}
else
{
InRemoveNode->Prev->Next = InRemoveNode->Next;
InRemoveNode->Next->Prev = InRemoveNode->Prev;
}
delete InRemoveNode;
}
}메인 코드
int main()
{
LinkedList* List = new LinkedList();
if (List != nullptr)
{
List->Add(5);
List->Add(9);
List->Add(7);
List->Insert(3, 1);
std::cout << "==제거 하기전 출력==" << std::endl;
List->Show();
Node* RemoveNode = List->Search(9);
if (RemoveNode != nullptr)
{
List->Remove(RemoveNode);
}
std::cout << "==제거 후 출력==" << std::endl;
List->Show();
}
}Add함수를 통해 5,9,7을 추가 해주고
Insert함수를 통해 3의 데이터를 1번째에 삽입시켜주면 5,3,9,7이 출력되며
Search함수로 9의 데이터를 찾은 후 제거해준다
그럼 5,3,7 이 출력된다.
'자료구조' 카테고리의 다른 글
| [자료구조] 스택 응용 - 사칙연산 계산기 (1) (0) | 2023.07.23 |
|---|---|
| [자료구조] 스택(Stack) - 링크드 리스트를 이용한 구현 (0) | 2023.07.21 |
| [자료구조] 스택(Stack) - 배열을 이용한 구현 (0) | 2023.07.21 |
| [자료구조] 환형 링크드 리스트(Circular Linked List) (0) | 2023.07.21 |
| [자료구조] 싱글 링크드 리스트(Single Linked List) (0) | 2023.07.18 |
