자료구조 - Linked List(Circular, Doubly Linked list)

Sorted List에서 가장 마지막에 값을 추가하거나 삭제를 해야할 때 매번 N번의 연산을 통해서 마지막 노드를 접근할 수 있다.

 

이러한 과정은 효율적이지 못하므로 마지막 값을 따로 접근할 수 있는 방법이 있으면 좋다.

 

따라서 원형 연결 리스트를 통해서 마지막 노드의 다음 노드로 가장 첫 번째 노드를 지정해 줘서 리스트의 ListData가 가장 마지막 노드를 포인팅하고 있으면 된다.

또한 Linked List로 삽입과 삭제를 구현할 때 다음 노드의 값에 따라 삽입 또는 삭제의 여부가 결정되기 때문에 구현하는 과정에서 다음 다음 노드의 값을 확인하던지 이전 노드를 가리키고 있는 포인터를 사용하였었다.

 

Circular Linked List를 python으로 구현하면 다음과 같다.

 

class CircularLL:
    def __init__(self):
        self.listData = None
        self.length = 0
        self.currentPos = None

    def is_full(self):
        try:
            location = NodeType("test")
            return False
        except:
            return True

    def length_is(self):
        return self.length

    def make_empty(self):
        while self.listData != None:
            tempPtr = self.listData.next
            del self.listData
            self.listData = tempPtr
        self.length = 0

    def find_item(self, listData, item):
        location = listData
        find = False
        moreToSearch = location != None

        while moreToSearch and not found:
            if location.info < item:
                location = location.next
                moreToSearch = location != None
            elif location.info == item:
                found = True
            else:
                moreToSearch = False
        return find
    
    def insert_item(self, item):
        location = self.listData
        newnode=NodeType(item)
        newnode.info=item
        if location == None:
            newnode.next = newnode
            self.listData = newnode
        else:
            predLoc = location
            full_check = True
            while location.next.info != self.listData.info:
                predLoc = location
                location = location.next
                if location.info >= item:
                    full_check = False
                    break
            if full_check:
                self.listData = newnode
            newnode.next=location
            predLoc.next=newnode
        self.length += 1

    def delete_item(self, item):
        location = self.listData.next
        pred = self.listData
        while item != location.info:
            pred = location
            location = location.next
        if location.info == self.listData:
            self.listData = pred
        pred.next = location.next
        self.length -= 1
   
    def reset_list(self):
        self.currentPos = None

    def get_next_item(self):
        if self.currentPos == None:
            self.currentPos = self.listData
        else:
            self.currentPos = self.currentPos.next
        return self.currentPos.next.info

    def __str__(self):
        self.reset_list()
        items = []
        for i in range(0, self.length):
            t = self.get_next_item()
            items.append(str(t))
        return "\n".join(items)

 

하지만 이러한 방법 대신에 현재 노드에 다음 노드와 이전 노드 모두 연결된 Doubly Linked list를 사용하면 다른 추가적인 요소가 필요 없이 문제가 해결 가능하다.

 

Doubly Linked list에서 Insert를 할 때 순서를 조심해야한다.

 

왜냐하면 내가 알 수 있는것은 새로운 노드의 주소와 현재 노드의 주소밖에 없는데 삽입하는 순서를 잘못하면 이전 노드를 찾을 수가 없어질 수 있기 때문이다.

 

만약 노드를 쭉 탐색하다가 삽입하기 적절한 위치를 찾게 되면 먼저 삽입해야할 새로운 노드의 전과 후를 각각 찾은 위치의 전과 지금의 위치에 대응시켜야한다.

 

즉, newNode->back = location->back이고, newNode->next = location으로 해주면 된다.

 

이제 나머지 연결도 마저해주면 되는데 현재 location의 위치가 삽입될 노드의 다음에 해당하기 때문에 이전 노드를 먼저 새로운 노드와 연결해주고 나서 현재 노드를 연결해주면 된다.

 

따라서 location->back->next = newNode로 먼저 해주고, location->back = newNode로 처리해주면 노드의 삽입이 끝난다.

 

이러한 내용을 바탕을 insert를 코딩해주면 다음과 같이 할 수 있다.

void SortedType::InsertItem(ItemType item) {
	NodeType* newNode;
	NodeType* location;
	bool found;
	newNode = new NodeType;
	newNode->info = item;
	if (listData != NULL) {
		FindItem(listData, item, location, found);
		if (location->info > item) {
			newNode->back = location->back;
			newNode->next = location;
			if (location != listData)
				(location->back)->next = newNode;
			else
				listData = newNode;
			location->back = newNode;
		}
		else {
			newNode->back = location;
			location->next = newNode;
			newNode->next = NULL;
		}
	}
	else {
		listData = newNode;
		newNode->next = NULL;
		newNode->back = NULL;
	}
	length++;
}

 

코딩을 하면서 예외적인 부분을 모두 처리해줬는데 먼저 리스트가 비어있는 경우는 새로운 노드를 바로 리스트로 만들어주었고, 삽입해야할 위치가 제일 끝인경우 삽입될 노드의 다음 노드가 없으므로 이부분을 따로 처리해 주었다.

 

그리고 삽입해야할 위치가 가장 앞인 경우도 삽입될 노드의 앞의 노드가 없으므로 이 또한 따로 처리해주면 된다.

 

이처럼 자료구조를 하다보면 항상 첫 부분과 마지막 부분에서 예외사항이 발생하는 것을 볼 수 있다.

 

따라서 매번 if-else구분으로 특수 사항을 처리해 줄 수 있지만 정렬된 리스트에서 무조건 앞이나 뒤에 오는 원소를 가진 노드를 추가해주는 것도 하나의 방법이다.

 

예를들어 사람의 이름을 저장한 리스트가 있다고 할 때 "AAAA"가 저장되어있는 노드와 "ZZZZ"가 저장되어있는 노드가 있으면 해당 노드들은 각각 양 끝단에 항상 위치하기 때문에 원소를 추가하거나 삭제할 때 발생하는 예외사항을 따로 처리하지 않아도 된다.

 

다만 이러한 방법은 필요 없는 메모리를 써야하는 단점이 있고, 리스트의 값을 확인할 때 양 끝단은 확인하지 않게 다시 조정해줘야하는 문제가 있다.

 

파이썬으로 Doubly Linked list를 구현하면 다음과 같이 짤 수 있다.

class DoublyLL:
    def __init__(self):
        self.head = NodeType('head')
    
    def find_item(self, item):
        location = self.head
        find = False
        moreToSearch = location != None
        while moreToSearch and not found:
            if location.info < item:
                location = location.next
                moreToSearch = location != None
            elif location.info == item:
                found = True
            else:
                moreToSearch = False
        return find
    
    def insert_item(self, item, new):
        location = self.head
        while location is not None:
            if location.info == item:
                break
            location = location.next
        new_node = NodeType(new)
        new_node.back = location
        new_node.next = location.next
        if location.next is not None:
            location.next.back = new_node
        location.next = new_node

    def delete_item(self, item):
        temp = self.head
        if temp.info == item:
            self.head = temp.next
            del temp
        else:
            while temp.next:
                temp2=temp.next
                if temp2.info==item:
                    temp.next=temp2.next
                    del temp2
                    return
                else:
                    temp=temp2
            
    def __str__(self):
        cur_node = self.head
        items = []
        while cur_node is not None:
            items.append("(" + str(cur_node.info) + ")\n")
            cur_node = cur_node.next
        return "".join(items)