단일 연결 리스트

* 단일 연결 리스트의 구조

typedef struct Node {               // (정체성 : struct Node)
    int data;          // 데이터 저장   (정체성 : int)
    struct Node* next; // 다음 노드를 가리키는 포인터  (정체성 : struct Node *)
} Node;

 

 

* 단일 연결 리스트의 기본 연산

1.노드 추가(Append)  :  리스트의 끝에 새로운 노드를 추가하는 기능

 

 

2. 노드 삭제(Delete)  :  특정 값을 가진 노드를 삭제하는 기능

 

3. 노드 탐색(Search)  :  특정 값을 가진 노드를 찾는 기능

 

4. 노드 출력(Display)  :  리스트의 모든 노드를 순차적으로 출력하는 기능

 

 

 

* 단일 연결 리스트의 장점과 단점

장점

• 동적 메모리 할당을 통해 크기를 유동적으로 조절 가능
• 노드 삽입 및 삭제가 빠름 (배열과 달리 요소를 이동할 필요 없음)

단점

• 임의 접근(random access)이 불가능하여 탐색 속도가 느림
• 추가적인 메모리 공간(next 포인터)이 필요

---

 

 

[ (void) insert_end 함수 (list , data) ]
createnode 함수가 따로 없고 append 함수에서 새 노드를 할당한다

(새 노드)  새 노드를 선언하고 할당하고
(초기화)   바로 초기화화기

(case 1)   if문으로 노드가 없는 경우
                head노드와 new_node 연결해서 새로운 노드 추가하기

(case 2)   temp 노드 만들고 while문으로 끝노드까지 이동한후
                new_node와 연결해서 새로운 노드 추가하기

---

여기에서는 끝노드에 노드추가를 하는데
중간에 노드를 추가할 때는

코드 순서가 중요하다

 

new_node->next = temp->next;              // 무조건 new_node 포인터를 먼저 연결한다고 생각하면 편하다

temp->next = new_node;

---

첫번째 위치에 삽입과   중간 위치에 삽입은 무조건 코드가 다를 수 밖에 없다
영향을 받는 노드의 개수부터가 차이가 나기 때문에
2가지 경우는 무조건 따로 분류해야 한다

---

[ (void) delete 함수 (list, key) ]

(case 1)  노드가 없는 경우 예외처리

(서포터 변수)  도우미 변수 temp, prev 선언 후 초기화

(case 2)    삭제할 노드가 1번째 노드인 경우
                  head가 temp 다음 노드를 가리키게 하고,  temp 메모리 해제

(case 3-1)  삭제할 노드가 2~N번째인 경우
                   while문으로 순회해서 key를 이용해 삭제할 노드 찾기 --> prev에 계속 전 노드를 담아두기
          
(case 4)    삭제할 노드가 없는 경우  -->  return;

(case 3-2)   prev가 temp 다음 노드를 가리키게 하고,  temp 메모리 해제

 

 

단일연결리스트의 1번째 위치 삭제에서는
prev노드가 없기 때문에

head 와 temp 포인로 삭제를 한다

단일연결리스트의  중간 위치의 삭제연산에서는
prev로 연결을 하고
temp는 해제를 위해 찾아야 한다

---

[ (Node *) search 함수 (list, key) ]

(서포터 변수)   temp 를 head로 초기화

(case 1)   while문으로 temp가  NULL일때까지  temp = temp->next; 로 순회해서 key를 찾으면 temp를 반환

(case 2)   찾는 노드가 없는 경우  return NULL;

---

[ (void) display 함수 (list) ]

(서포터 변수) temp 를 head 로 초기화

(순회)  while문으로 temp 가  NULL일 때까지 출력하고   temp = temp->next;  로 순회하기

(가독성)  printf("NULL\n");  해서 가독성 높이기

 

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {     // 노드 구조체
    int data;
    struct Node* next;
} Node;

typedef struct LinkedList {   // 단일 연결 리스트 구조체
    Node* head;                // head 노드
} LinkedList;

void insert_end(LinkedList* list, int data) {
    Node* new_node = (Node*)malloc(sizeof(Node));   // 새 노드 메모리 동적할당
    new_node->data = data;
    new_node->next = NULL;

    if (list->head == NULL) {     // 노드가 없을 때
        list->head = new_node;
        return;
    }
    
    Node* temp = list->head;
    while (temp->next != NULL) {   // 끝노드까지 이동
        temp = temp->next;
    }
    temp->next = new_node;
}

void delete(LinkedList* list, int key) {
    if (list->head == NULL) return; // 리스트가 비었을 때 예외 처리 (방어코드)
    
    Node* temp = list->head;   // temp를 head노드로 초기화
    Node* prev = NULL;
    
    if (temp != NULL && temp->data == key) {  // 삭제할 노드가 리스트의 첫 번째 노드일 때(head 노드일 때)
        list->head = temp->next;  // 리스트의 head를 temp->next로 이동 -> 즉, head를 두 번째 노드로 변경
        free(temp);
        return;
    }
    
    while (temp != NULL && temp->data != key) {  // 삭제할 노드가 2~N번째 노드일 때
        prev = temp;          // prev에 temp 담아두기
        temp = temp->next;    // 이 코드가 prev = temp; 다음에 나와야 함
    }
    
    if (temp == NULL) return;  // 삭제할 노드가 없는 경우
    
    prev->next = temp->next;
    free(temp);
}

Node* search(LinkedList* list, int key) {
    Node* temp = list->head;
    while (temp != NULL) {
        if (temp->data == key) {
            return temp;
        }
        temp = temp->next;
    }
    return NULL;
}

void display(LinkedList* list) {
    Node* temp = list->head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
    LinkedList list;
    list.head = NULL;

    append(&list, 1);
    append(&list, 2);
    append(&list, 3);
    display(&list);  // 1 -> 2 -> 3 -> NULL
    
    delete(&list, 2);
    display(&list);  // 1 -> 3 -> NULL
    
    Node* found = search(&list, 3);
    if (found) {
        printf("노드 %d 찾음\n", found->data);
    } else {
        printf("노드 찾을 수 없음\n");
    }
    
    return 0;
}

 

---

 

void append(LinkedList* list, int data) {
    Node* new_node = (Node*)malloc(sizeof(Node));   // 새 노드 메모리 동적할당
    new_node->data = data;
    new_node->next = NULL;

    if (list->head == NULL) {     // 1번째 노드일때
        list->head = new_node;
        return;
    }
    
    Node* temp = list->head;
    
    while (temp->next != NULL) {   // 끝노드까지 이동
        temp = temp->next;
    }
    temp->next = new_node;
}

 

 

---

 

 

궁금증 : new_node 는 메모리를 할당할 때 동적할당으로 밖에 못하나?  다른 방법은 없나?

 

 

---

 

더 완성도 있는 코드를 작성하려면~