자료구조...18

이중 연결 리스트 구현

단일 연결 리스트의 이해를 기반으로 C#의 LinkedList<T>를 간략화하여 int만 저장할 수 있는 DoublyLinkedList를 만든다.

 

구현이 필요한 메서드 및 속성은 다음과 같다.

 

• 생성자
  • DoublyLinkedList() 비어있는 인스턴스 생성
  • DoublyLinkedList(DoublyLinkedList&) 다른 DoublyLinkedList 데이터로 인스턴스 생성
• 속성 
  
  • Count 사용되고 있는 노드의 수
  • First 리스트의 처음 노드
  • Last 리스트의 마지막 노드
• 메서드 
  • AddFirst(data) 시작 위치에 데이터를 포함한 노드 생성 후 삽입
  • AddFirst(node) 지정된 노드 삽입
  • AddLast(data) 시작 위치에 데이터를 포함한 노드 생성 후 삽입
  • AddLast(node) 지정된 노드 삽입
  • Insert(int, data) 지정된 위치에 데이터를 포함한 노드 생성 후 삽입
  • Insert(int, node) 지정된 위치에 지정된 노드 삽입
  • RemoveFirst(data) 가장 처음 일치한 데이터를 포함한 노드 삭제
  • RemoveLast(data) 가장 마지막 일치한 데이터를 포함한 노드 삭제
  • Remove(node) 지정된 노드와 동일한 노드 삭제
  • Clear() 모든 노드 삭제
  • Contains(data) 데이터를 포함한 노드의 존재 여부 확인
  • Contains(node) 지정된 노드의 존재 여부 확인
  • Find(data) 가장 처음 일치한 데이터를 포함하는 노드 반환
  • FindLast(data) 가장 마지막 일치한 데이터를 포함하는 노드 반환

 

DoublyLinkedList.h

#pragma once
#include <xutility>
#include <iostream>

struct DoublyLinkedListNode
{
	DoublyLinkedListNode() {}
	DoublyLinkedListNode(int value) { m_data = value; }

	int m_data = 0;
	DoublyLinkedListNode* m_prev = nullptr;
	DoublyLinkedListNode* m_next = nullptr;
};

class DoublyLinkedList
{
public:
#pragma region 생성자
	DoublyLinkedList();
	DoublyLinkedList(const DoublyLinkedList& other);
	~DoublyLinkedList();
#pragma endregion

#pragma region 속성
	const int Count() { return m_count; }
	DoublyLinkedListNode& First() { return *m_head; }
	DoublyLinkedListNode& Last() { return *m_tail; }
#pragma endregion

#pragma region 메서드
	void AddFirst(int value);
	void AddFirst(DoublyLinkedListNode* node);
	void AddLast(int value);
	void AddLast(DoublyLinkedListNode* node);
	void Insert(int index, int value);
	void Insert(int index, DoublyLinkedListNode* node);

	bool RemoveFirst(int value);
	bool RemoveLast(int value);
	void Remove(const DoublyLinkedListNode* node);
	void Clear();

	bool Contains(int value);
	bool Contains(const DoublyLinkedListNode* node);
	DoublyLinkedListNode* Find(int value);
	DoublyLinkedListNode* FindLast(int value);

	void PrintInfo();
#pragma endregion

private:
#pragma region Class Util
	DoublyLinkedListNode* PopNode(int value);
	void PushNode(DoublyLinkedListNode* node);
#pragma endregion
	
private:
#pragma region 변수
	size_t m_count;
	DoublyLinkedListNode* m_head;
	DoublyLinkedListNode* m_tail;
	DoublyLinkedListNode* m_free;
#pragma endregion
};

 

참고문헌

Microsoft MSDN.LinkedList<T> 클래스 (System.Collections.Generic)