Doubly Linked

Circular Linked List

마지막 원소의 next를 NULL이 아니라 맨 앞으로 보낸다.

마지막이 포인팅 하고 있는게 listData면 그 노드가 마지막이었다는 걸 알 수 있음.

Circular Linked list

Doubly Linked List

원래 private으로 info, next만 가지고 있었는데 추가로 back 포인터를 만들자.

이제 InsertItem 할 때 predLoc를 따로 생성할 필요가 없어졌다.

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

InsertItem

리스트의 정보가 손실되지 않도록 순서를 잘 설정해주어야 한다.

새로운 노드의 back과 next를 먼저 설정해주어야 기존 리스트를 건드리지 않을 수 있다. 

InsertItem

1. newNode -> back = location -> back;

2. newNode -> next = location;

3. location -> back -> next = newNode;

4. location -> back = newNode;

 

FindItem(listData,item,location,found)

RetrieveItem, InsertItem, DeleteItem 할 때 항상 요소들을 하나씩 살펴보고 location의 위치를 확정하는 등의 작업이 필요하다.

이 과정을 FindItem 하나로 묶어보자.

template <class ItemType>
void FindItem(NodeType<ItemType>*listData, ItemType item, 
			  NodeType<ItemType>* &location, bool& found){
          
          bool moreToSearch = true;
          location = listData;
          found = false;
          
          while(!found && moreToSearch){
          	if(item > location -> info){
            	moreToSearch = false;
                }
            else if (item == location -> info){
            	found = true;
                }
            else{
            	if(location -> next == NULL){
                	moreToSearch = false;
                    }
                else{
                	location = location -> next;
                	}
            }
        }

 

Inserting into a Doubly Linked List

back, next를 잘 지정해주면 insert 할 때 아무 문제가 없는 것 같지만, 리스트의 맨 앞에 새로운 아이템을 넣을 때 문제가 발생한다.

맨 앞 노드의 back을 연결할 곳이 없기 때문이다. 따라서 이 경우를 예외로 처리한다.

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){
    	FindItem(listData,item,location,found);     //여기서 들어갈 위치 확정.(location)
        
        if(item < location -> info){                //location보다 앞에 들어가야 할 경우
        	newNode -> back = location -> back;
            newNode -> next = location;
            if(location != listData){
            	(location -> back) -> next = newNode;
                }
                else{
                    listData = newNode;
                    }
            location -> back = newNode;
    	}
            else{                                    //Insert at the end!!
                newNode -> back = location;
                location -> next = newNode;
                newNode -> next = NULL;
                } 
        else{                                        //Insert into an empty list
        	listData = newNode;
            newNode -> next = NULL;
            newNode -> back = NULL;
            }
        length ++;
    }