연결리스트

연결리스트는 선형리스트와는 달리 논리적인 순서와 물리적인 순서가 일치하지 않아도 된다.
연결리스트는 순차적으로 다음 원소를 표현한 것이아니라, 각 원소에 다음 원소는 주소 링크에 의해 연결되어 있다.

연결 리스트는 <원소,주소>단위로 구성된 노드로 구성되어 있다.

data	link

이러한 형태를 띄며, 포인터를 이용하여 연결한다.

순차 자료구조(선형 리스트)는 삽입이나 삭제를 할때 뒷부분 원소를 모두 이동해야 했다. 하지만, 연결리스트는 삽입,삭제를 한후 링크만 연결해주면 되므로, 삽입,삭제에 유리하다.

노드는 다음과 같이 구조체로 정의 가능하다.

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

단순 연결 리스트(Singly Linked List)

단순 연결 리스트는 노드의 링크 필드가 하나이며, 링크 필드는 다음 노드와 연결되는 구조이다.

삽입

단순 연결 리스트 에서의 삽입은 다음과 같은 준비과정을 가진다.
1.삽입할 노드준비
2.새 노드의 데이터 필드에 값을 저장
3.새 노드의 링크값을 지정
4.리스트의 앞 노드에 새 노드를 연결

그림으로 보자.

1. 삽입할 노드 준비: 삽입할 새노드로 만들 공백 노드(150번지)를 메모리에서 할당 받는다. 포인터 변수 new가 새 노드를 가리키게 한다.
   

 

2.새노드의 데이터 필드값 저장:new 노드의 데이터 필드에 '수'를 저장한다.

 





3.새 노드의 링크 필드값 지정 :새로운 노드의 링크가 200을 가리키게해 '금' 앞에 올 수 있게 한다. '월' 다음에는 '수'가 와야하므로 '월'의 기존 링크는 끊고 '수'와 연결한다.

4.리스트의 앞 노드에 새 노드 연결

삭제

단순 연결 리스트에서 삭제하는 방법은 다음과 같다.
1. 삭제할 노드의 앞 노드를 찾는다.
2. 앞 노드에 삭제할 노드의 링크 필드값을 저장한다.
3. 삭제한 노드의 앞 노드와 삭제한 노드의 다음 노드를 연결한다.

예를들어,head -> (월,150)->(수,200)->(금,300)->(일,NULL)// (data,link)
이러한 단순 연결리스트에서 '수'를 삭제한다고 해보자.

1.삭제할 노드의 앞노드 '월'을 찾는다.
2.'월' 노드의 링크필드에 삭제할 노드인 '수'노드의 링크값을 넣는다.
head -> (월,200) (수,200)->(금,300)->(일,NULL)
3.삭제한 노드의 앞 노드와 삭제한 노드의 다음 노드를 연결한다.
head -> (월,200)->(금,300)->(일,NULL)

지금 상태에서는 '수'노드가 '금'노드에 연결되어 있지만, 앞에 노드에서 연결이 끊어졌기 때문에 논리적으로 제외된 값이 되었다.

리스트에 첫번째 노드로 삽입하는 알고리즘

1. 삽입할 노드에 대한 메모리를 할당받아서 포인터 new에 설정한다.
   new -> ( , )
2. 새 노드에 데이터 x를 저장한다.
   new -> (x,)
3. 리스트의 첫 번째 노드 주소(L,100)를 삽입할 새 노드 new의 링크 필드에 저장하여, 삽입한 새노드 new가 100번지에 있는 리스트의 첫번째 노드로 연결 되도록 한다. //주소(data,link)

4. 리스트의 첫번째 노드 주소를 저장하고 있는 L이 new node의 주소를 저장하여 포인터L을 새 노드 리스트의 첫번째 노드로 연결한다.
   

리스트 중간에 노드 삽입하는 알고리즘

1. 단순 연결리스트가 공백인 경우
   L이 NULL인 경우다. 즉, 연결리스트가 아무것도 없는 경우이다.
   이러한 경우에는, new node가 첫번째 노드가 되도록 L이 new node의 주소값을 가리키도록 한다.

2. 공백 리스트가 아닌경우
   new node를 200번지와 100번지 사이에 넣을때에는
   pre가 가리키고 있는 링크필드 값을 new node의 주소(700)를 갖도록 한다. new node의 링크필드는 주소값 200을 갖는다.
   

리스트 마지막에 노드를 삽입하는 알고리즘

• 공백 리스트인 경우
  L이 공백인 경우이다. 즉, 연결리스트가 하나도 없을때 이다.
  L이 new node를 가리키도록 한다.

• 공백 리스트가 아닌경우
  먼저 마지막 노드를 찾아야 한다. 마지막 노드는 링크값이 NULL인 노드이다.
  순회 포인터 temp를 통해서 링크값이 NULL이 나올때까지 순회한다.
  NULL이나오면 해당 노드의 링크값이 new node를 가리키도록 한다.

구현

[InsertLinkedList.h]

#pragma once
//단순 연결리스트의 노드 구조를 구조체로 정의
typedef struct ListNode{
	char data[4];
    struct ListNode* link;
}listNode;

//리스트 시작을 나타내는 head 노드를 구조체로 정의
typedef struct{
	listNode* head;
}linkedList_h;

linkedList_h* createLinkedList_h(void);
void freeLinkedList_h(linkedList_h* L);
void printList(linkedList_h* L);
void insertFirstNode(linkedList_h* L,char* x);
void insertMiddleNode(linkedList_h* L,listNode* pre, char* x);
void insertLastNode(linkedList_h* L,char* x);

[InsertLinkdeList.c]

#define _CRT_SECURE_NO_WARNINGS
#include <string.h>
#include <stdlib.h>
#include "InsertLinkedList.h"
//공백 연결리스트를 생성하는 연산
linkedList_h* createLinkedList_h(void){
	linkedList_h* L;
    L = (linkedList_h*)malloc(sizeof(linkedList_h));
    L ->head = NULL; // 공백 리스트이므로 NULL설정
    return L;
}

//연결 리스트의 전체 메모리를 해제하는 연산
void freeLinkedList_h(linkedList_h* L){
	listNode* p;
    while(L->head != NULL){
    	p = L->head;
        L->head = L->head->link;
        free(p);
        p=NULL;
    }
}

//연결 리스트를 순서대로 출력하는 연산
void printList(linkedList_h* L){
	listNode* p;
    printf("L=(");
    p = L->head;
    while(p != NULL){
    	printf("%s", p->data);
        p = p->link;
        if(p != NULL)printf(", ");
    }
    printf(")\n");
}

//첫번째 노드로 삽입하는 연산
void insertFirstNode(linkedList_h* L,char* x){
	listNode* newNode;
    newNode = (listNode*)malloc(sizeof(listNode)); //삽입할 새노드 할당
    strcpy(newNode->data,x); // 새 노드의 데이터 필드에 x 저장
    newNode->link=L->head;
    L->head = newNode;
}

//node를 pre 뒤에 삽입하는 연산
void insertMiddleNode(linkedList_h *L,listNode* pre, char* x){
	listNode* newNode;
    newNode = (listNode*)malloc(sizeof(listNode));
    strcpy(newNode->data,x);
    if(L->head == NULL){ // 공백 리스트인경우
    	newNode->link =NULL; //새 노드를 첫번째이자 마지막으로 연결
        L->head = newNode;
    }
    else if(pre == NULL){ // 삽입 위치를 설정하는 pre가 NULL인경우
    	newNode->link = L->head; //새 노드를 첫번째 노드로 삽입
        L->head = newNode;
	}
    else{
    	newNode->link =pre->link; // 포인터 pre의 노드 뒤에 새 노드 연결
        pre->link = newNode;
    }
}

//마지막 노드로 삽입하는 연산
void insertLastNode(LinkedList_h* L,char* x){
	listNode* newNode;
    listNode* temp;
    newNode = (listNode*)malloc(sizeof(listNode));
    strcpy(newNode->data,x);
    newNode ->link = NULL;
    if(L->head == NULL){ // 현재 리스트가 공백인경우
   		L->head = newNode; // 새 노드를 리스트의 시작 노드로 연결
        return;
    }
//현재 리스트가 공백이 아닌경우
	temp = L->head;
    while(temp->link != NULL) temp = temp->link; // 현재 리스트의 마지막 노드를 찾음
    temp->link = newNode;// 새노드를 마지막 노드(temp)의 다음 노드로 연결
}

[main.c]

#include <stdio.h>
#include "InsertLinkedList.h"

int main(void){
	linkedList_h* L;
    L = createLinkedList_h();
    printf("(1) 공백 리스트 생성하기! \n");
    printList(L);
    
    printf("\n(2) 리스트에 [수] 노드 삽입하기!");
    insertFirstNode(L,"수");
    printList(L);
    
    printf("\n(3) 리스트 마지막에 [금] 노드 삽입하기!\n");
    insertLastNode(L,"금");
    printList(L);
    
    printf("\n(4) 리스트 첫 번째에 [월] 노드 삽입하기! \n");
    insertFirstNode(L,"월");
    printList(L);
    
    printf("\n(5) 리스트 공간을 해제하여 공백 리스트로 만들기! \n");
    freeLinkedList_h(L);
    printList(L);
    
    getchar(); return 0;
	
}

참조

• c로 배우는 쉬운 자료구조