Circular Linked Lists

생성일: 2021년 10월 29일 오후 11:36

기존의 Linked Sorted List를 Circular 형식으로 몇 개의 함수를 재구성 하였다.

listData변수가 가장 마지막 노드를 가리키게 하고 마지막 노드는 첫번째 노드를 가르키게 한다.

circle.cpp

//Linked Sorted List의 일부 함수들을 Circular Linked List로 재구성 한 것 => 이 코드 자체로 컴파일 되지 않는다.
//일부의 함수만 정의되어 있다.

template <class ItemType>
struct NodeType;

template <class ItemType>
class SortedType
{
public:
	SortedType();
	~SortedType();
	bool IsFull() const;
	int LengthIs() const;
	void MakeEmpty();
	void RetrieveItem(ItemType& item, bool& found);
	void InsertItem(ItemType item);
	void DeleteItem(ItemType item);
	void ResetList();
	void GetNextItem(ItemType&);

private:
	NodeType<ItemType>* listData;
	int length;
	NodeType<ItemType>* currentPos;
};

template <class ItemType>
struct NodeType
{
  ItemType info;
  NodeType* next;  
};

template<class ItemType>
void FindItem(NodeType<ItemType>* listData, 
              ItemType item,
              NodeType<ItemType>*& location, 
              NodeType<ItemType>*& predLoc,
              bool& found)
// Pre: List is not empty.
{
  bool moreToSearch = true;

  location = listData->next;    //listData가 제일 끝을 가리키고 있기 때문에 제일 첫 노드를 가리키기도록 location 설정
  predLoc = listData;
  found = false;

  while (moreToSearch && !found)
  {
    if (item < location->info)
      moreToSearch = false;
    else if (item == location->info)
      found = true;
    else
    {
      predLoc = location;
      location = location->next;
      moreToSearch = (location != listData->next);  //다시 제일 처음 노드가 되기 전까지 반복문 수행
    }
  }
}

template<class ItemType>
void SortedType<ItemType>::InsertItem(ItemType item)
{
  NodeType<ItemType>* newNode;
  NodeType<ItemType>* predLoc;
  NodeType<ItemType>* location;
  bool found;
  
  newNode = new NodeType<ItemType>;
  newNode->info = item;
  if (listData != NULL)
  {
    FindItem(listData, item, location, predLoc, found);
    newNode->next = predLoc->next;
    predLoc->next = newNode;
    // If this is last node in list, reassign listData.
    if (listData->info < item)
      listData = newNode;
  }
  else // Inserting into an empty list.
  {
    listData = newNode;
    newNode->next = newNode;
  }
  length++;
}

template<class ItemType>
void SortedType<ItemType>::DeleteItem(ItemType item)
{
  NodeType<ItemType>* location;
  NodeType<ItemType>* predLoc;
  bool found;
  
  FindItem(listData, item, location, predLoc, found);
  if (predLoc == location) // Only node in list?
    listData = NULL;
  else
  {
    predLoc->next = location->next;
    if (location == listData) // Deleting last node in list?
      listData = predLoc;
  }
  delete location;
  length--;
}