연결리스트

● 연결리스트

구조체의 멤버 안에 자기자신과 같은 노드를  가리키는 주소를 가지고 있어야 한다.   -> 자기 참조 구조체
헤드노드라고 부르는 첫 번째 노드의 포인터가 중요하다.

typedef struct list_node *list_pointer;
struct list_node {
    char data[5];
    list_pointer link;
};
list_pointer ptr = NULL;


① 노드 삽입
void append(simple_pointer ptr, simple_pointer inode)
{   
    simple_pointer before;

    while ( ptr != NULL ) {
        before = ptr;
        ptr = ptr -> next;
    }
    before -> next = inode;
    inode -> next = NULL;
}
 
② 리스트 출력
void print_list(simple_pointer ptr)
{
    printf("The single linked list contains : \n");
    while ( ptr != NULL ) {   
        printf("%s : %d\n", ptr->state, ptr->count);
        ptr = ptr -> next;
    }
}

● 원형 연결 리스트

단순 연결 리스트의 마지막 노드의 포인터는 NULL이었다. 이 링크를 사용하기 위하여 마지막 노드의 포인터를 NULL이 아닌 첫 번째 노드(head node)의 주소를 가리키도록 할 때, 이 리스트를 원형 연결 리스트라고 한다.

-어느 하나의 노드로부터 다른 모든 노드로 접근이 가능하다.
-리스트의 하나의 노드를 찾을 때, 무한 루프에 빠질 염려가 있다.
-마지막 노드를 가리킴으로써 리스트의 앞이나 뒤에 노드를 삽입할 수 있다.

① 길이 계산
int length(list_pointer ptr)
{
    list_pointer temp;
    int count = 0;
    if (ptr) {
        temp = ptr;
        do {
            count++;
            temp = temp -> link;                    <--> print 소스로 변경하면 출력
        } while(temp != ptr);
    }
    return count;
}
 

② 노드 삽입 ( front )
void insert_front(npointer node)
{
    if (!ptr) {
        ptr = node;
        node -> link = node;
    } else {
        node -> link = ptr -> link;                            
        ptr -> link = node;                         <--->  ptr = node 를 추가하면 후방삽입 개념
    }
}

● 이중 연결 리스트

단순 연결 리스트는 단지 링크의 방향으로만 쉽게 이동할 수 있다는 제한점이 있다.
따라서, 삭제와 같은 연산과 같은 포인터를 양방향으로 이동해야 할 필요가 있는 문제에 대해서는,
이중 연결 리스트를 사용하는 것이 편리하다.

typedef struct node *node_pointer;
struct node {
    node_pointer llink;
    element item;
    node_pointer rlink;
};
아래 공식이 성립
ptr  =  ptr -> llink -> rlink  =  ptr -> rlink -> llink    

① 노드 삽입
void dinsert(node_pointer node, node_pointer newnode)
{
    newnode -> llink = node;
    newnode -> rlink = node -> rlink;
    node -> rlink -> llink = newnode;
    node -> rlink = newnode;
}

② 노드 삭제
void ddelete(node_pointer node, node_pointer deleted)
{
    if (node == deleted)
        printf("Deletion of head node not permitted. \n");
    else {
        deleted -> llink -> rlink = deleted -> rlink;
        deleted -> rlink -> llink = deleted -> llink;
        free(deleted);
    }
}