자료구조(3) 단순 연결 리스트

쓰고싶을때 쓰는 글

 

이번에는 단순 연결 리스트에 대해서 공부를 하였다.

순차 자료구조인 선형리스트와 달리 단순 연결 리스트는 연결 자료구조이다. 즉 데이터의 논리적인 순서와 물리적인 순서가 일치하지 않아도 된다.

 

아무튼 본론으로 돌아와서 단순 연결 리스트에 대해서 설명하겠다.

연결 리스트는 선형 리스트(배열)과는 다르게 포인터를 통해서 구현 하였다. 전에 쓴 글에서 선형 리스트는 요소의 삭제와 위치 변경간에 낭비가 심하다고 하였다. 그에 따라 선형 리스트보다는 지금 보기에는 좀 불편해 보이지만, 배열의 물리적인 순서를 맞추기 위한 오버헤드 낭비측면에서는 훨씬 낫다고 볼수 있다.

 

연결리스트는 포인터를 통해 구현했다. 이게 무슨말이냐.... 기차를 떠올려봐라. 각 기차칸은 다음 기차칸과 연결이 되어있는데, 이 구조에서 각각의 기차칸은 Node로 data를 저장할수 있고, 다음 기차칸으로 갈수 있는 통로를 갖고있다. 이 통로를 포인터라고 보면된다. 아래의 코드롤 보아라.(기본적인 틀이다.)

typedef struct Node{
	int num;
    struct Node* link;
};

num은 각 기차칸에서 저장하는 data  구조체 포인터인 link는 다음 기차칸의 통로 역할을 한다. 

(솔직히 자료구조를 공부하면서 살짝 충격을 먹었다. 지금까지 문법공부하던것과는 다른 새로운걸 배운 느낌을 받았는데, 이 연결리스트 부분에서 이런 느낌이 가장 강하게 들었다. )

그래서 처음 공부하는 입장에서는 구조체 포인터도 받아들이기 힘들거고 왜 이렇게 불편하게 하는지도 이해하기 힘들것이다. 

하지만 연결리스트는 삽입과 삭제의 과정에서 위의 포인터주소만 바꿔주면 된다. 

삭제할때는 삭제하려는 노드의 앞 노드를 찾아서 앞노드의 포인터를 삭제하려는 노드의 다음 노드와 연결하면 된다. 

삽입할때는 삽입하려는 노드의 앞 노드의 포인터를 삽입하려는 노드를 가리키게 하면되고, 삽입하려는 노드는 기존 앞노드의 다음노드의 주솟값을 가리키게 하면 된다. 

 

대충봐도 배열보다 기회비용이 훨씬 좋아보인다. 

아래는 연결리스트와 관련된 함수이다. 알아서 공부하도록 하자.

typedef struct Node{
    char data[4];
    struct Node * link;
}node;

typedef struct {
    node * head;
}node_h;
//공백 연결리스트 생성
node_h* createNode_h(){
    node_h* N;
    N = (node_h*)malloc(sizeof(node_h));
    N->head = NULL;
    return N;
}
//연결 리스트 비우기
void freeLinkedlist_h(node_h* H){
    node * N;
    while (H->head != NULL){
        N = H->head;
        H->head = H->head->link;
        free(N);
        N=NULL;
    }
}
//리스트 출력 
void printList(node_h* H){
    node* N = H->head;
    while(N->link != NULL){
        printf("%s\n",N->data);
        N = N ->link;
    }
}
//첫번째 노드 삽입하기.
void insertFirstNode(node_h * H,char* s){
    node* temp = (node*)malloc(sizeof(node));
    strcpy(temp->data,s);
    temp->link = H->head;
    H->head = temp;
}
//노드를 pre다음에 삽입하기.
void insertMiddleNode(node_h * H,node* pre,char* s){
    node * temp = (node *)malloc(sizeof(node));
    strcpy(temp->data,s);
    if(H->head == NULL){
        H->head = temp;
        temp->link =NULL;
    }
    else if(pre == NULL){
        H->head = temp;
    }
    else {
        temp->link = pre->link;
        pre->link = temp;
    }
}
//마지막 노드로 삽입하기.
void insertLastNode(node_h * H,char* s){
    node * temp = (node *)malloc(sizeof(node));
    strcpy(temp->data,s);
    if(H->head == NULL){
        H->head = temp;
        temp->link =NULL;
        return;
    }
    temp -> link = H->head;
    while(temp->link->link != NULL)
        temp -> link = temp -> link->link;

    temp ->link ->link = temp;
    temp->link = NULL;
}
//p노드 삭제하기.
void deleteNode(node_h * H,node * p){
    if(H->head == NULL)
        return;
    node * temp = H->head;
    if(p == NULL) return;
    while(temp->link != p){
        temp = temp->link;
    }
    temp->link = p->link;
    free(p);
    p = NULL;
}
//s라는 데이터를 갖은 노드 찾기.
node* searchNode(node_h* H,char* s){
     node * temp = H->head;
     while(temp != NULL){
         if(strcmp(temp->data,s)==0) return temp;
         else temp = temp->link;
     }
    return temp;
}
//노드 순서 역순으로 바꾸기.
void reverse(node_h* H){
    node * p;
    node * q;
    node * r;
    p = H->head;
    q = NULL;
    r = NULL;
    while(p!=NULL){
        r = q;
        q = p;
        p = p->link;
        q ->link = r;
    }
    H->head = q;
}