[ 자료구조 ] linked list 원형 연결 리스트 이중 연결 리스트

[ 자료구조 ] linked list 원형 연결 리스트 이중 연결 리스트

linkedlist에서 뒤의 노드를 읽는 것은 링크로 연결해줘야 하기 때문에 읽기, 삭제하기, 삽입하기가 어렵다.

이를 개선하기 위해 원형 연결 리스트와 이중 연결 리스트가 등장했다.

 

연결 리스트의 데이터 개수가 n개 일 때 n번의 링크를 따라가야 한다 => O(n)

 

원형 연결 리스트

원형 연결 리스트 : 연결 리스트의 맨 끝 노드를 첫 번째 노드와 연결시켜 원형으로 만든 리스트이다.

맨 끝 링크는 맨 앞 노드를 가리킨다.

포인터는 맨 끝 노드를 가리킨다.

=> 맨 끝과 맨 앞을 바로 찾을 수 있다.

 

 

단순 원형 리스트	삽입	삭제
맨 처음	O(1)	O(1)
맨 마지막	O(1)	O(n)

 

원형 연결 리스트의 맨 뒤에 노드를 삽입하는 알고리즘

void insert_last(list_ptr * ptr, list_ptr node){

    if(IS_EMPTY(*ptr)){ // 빈 리스트의 경우
        *ptr = node;
        node->link = node;
    }
    else{ // 노드 연결
        node->link = (*ptr)->link;
        (*ptr)->link = node;
        *ptr = node;
    }
}

 

이중 연결 리스트

 

이중 연결 리스트란 연결 리스트의 각 노드에 링크를 2개 만들어 하나는 뒷 노드를 하나는 앞 노드를 가리키는 연결 리스트이다. 기존의 단순 연결 리스트는 노드 포인터를 알고 있을 때 노드의 다음 노드는 찾아갈 수 있지만, 노드 앞의 노드는 찾아갈 수 없다. 앞의 노드를 찾으려면 리스트의 처음부터 거슬러 올라가야 한다. 따라서 단순 연결 리스트의 각 노드에 두 개의 노드 포인터를 두어 하나는 앞쪽 노드를 가리키고, 다른 하나는 뒤쪽 노드를 가리켜 앞 뒤에 상관없이 어느 방향으로나 갈 수 있도록 만든 것이 이중 연결 리스트이다. 이러한 단점으로 인해 이중 연결 리스트가 사용된다.

 

 

728x90

 

 

이중 연결 리스트 노드 선언

struct dnode {
    struct dnode *llink;
    element item;
    struct dnode *rlink;
};

typedef struct dnode node;
typedef node *node_ptr;

 

ptr은 이중 연결 리스트를 가리킨다.

이중 연결 리스트에서는 ptr = ptr->llink->rlink = ptr->rlink->llink 식이 성립한다.

 

<이중 원형 연결 리스트에 노드를 삽입>

 

삽입할 노드의 바로 앞 노드만 알면 된다.

void dinsert(node_ptr node,node_ptr newnode) {
    newnode->llink = node;
    newnode->rlink = node->rlink; 
    node->rlink->llink = newnode; 
    node->rlink = newnode; 
}

<이중 원형 연결 리스트에 노드를 삭제>

void ddelete(node_ptr node,node_ptr deleted) {
    if(node == deleted)
        printf(“ head node  삭제 금지\n”);
    else {
        deleted->llink->rlink = deleted->rlink; 
        deleted->rlink->llink = deleted->llink;
        free(deleted); 
}
}