Doubly Linked List

생성일: 2021년 10월 30일 오전 12:10

Doubly Linked List에서 FindItem 과 InsertItem 함수를 구현했다.

double.cpp

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

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>
void FindItem(NodeType<ItemType>* listData, ItemType item, 
		    NodeType<ItemType>*& location, bool& found)
// Pre:  List is not empty.
{
  bool moreToSearch = true;

  location = listData;
  found = false;
  while (moreToSearch && !found)
  {
    if (item < location->info)
      moreToSearch = false;
    else if (item == location->info)
      found = true;
    else
    {
        location = location->next;
        moreToSearch = (location != NULL);
    }
  }
}

template<class ItemType>
void SortedType<ItemType>::InsertItem(ItemType item)
{
    NodeType<ItemType>* newNode;
    NodeType<ItemType>* location;
    bool found;

    newNode = new NodeType<ItemType>;
    newNode->info = item;

    if (listData != NULL) { //list가 비어있지 않다면
        FindItem(listData, item, location, found); //넣을 자리 찾기

        if (location->info > item) { // 넣어야 할 노드가 제일 마지막 위치가 아니라면
            newNode->back = location->back; // 1번 작업 : 새 노드의 back이 현재 location의 앞을 가리키게 함
            newNode->next = location; // 2번 작업
            if (location != listData) // 넣어야 할 노드가 제일 첫 번째 위치가 아니라면
                (location->back)->next = newNode; // 3번 작업
            else // 넣어야 할 노드가 제일 첫 번째 위치 일때 (3번작업 대신 실행)
                listData = newNode;
            location->back = newNode; // 4번 작업
        }
        else // 넣어야 할 노드가 제일 마지막 자리라면
        {
            newNode->back = location;
            location->next = newNode;
            newNode->next = NULL;
        }

    }
    else //비어있는 list라면
    {
        //비어있는 list에 처음 새 노드를 넣음
        listData = newNode;
        newNode->back = NULL;
        newNode->next = NULL;

    }
    length++;
}