자료구조...12

단일 연결 리스트 구현

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

 

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

 

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

 

SinglyLinkedList.h

#pragma once
#include <iostream>

class SinglyLinkedListNode
{
	SinglyLinkedListNode() {}
	SinglyLinkedListNode(int value) { m_data = value; }

	int m_data = 0;
	SinglyLinkedListNode* m_next = nullptr;
};

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

#pragma region 속성
	const int Count() { return m_count; }
	SinglyLinkedListNode& Front() { return *m_head; }
#pragma endregion

#pragma region 메서드
	void Add(int value);
	void Add(SinglyLinkedListNode* node);
	void Insert(int index, int value);
	void Insert(int index, SinglyLinkedListNode* node);

	void Remove(int index, int value);
	void Remove(int index, const SinglyLinkedListNode* node);
	void Clear();

	bool Contains(int value);
	bool Contains(const SinglyLinkedListNode& node);
	SinglyLinkedListNode& Find(int value);
	SinglyLinkedListNode& FindLast(int value);
#pragma endregion

private:
#pragma region 변수
	size_t m_count;
	SinglyLinkedListNode* m_head;
#pragma endregion
};

 

참고문헌

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

Microsotf MSDN.forward_list 클래스