연결 리스트 & 이중포인터

연결 리스트(linked list)

• 노드라 불리는 구조체의 체인이다.
• 각 노드들은 다음 노드를 가르키는 포인터를 가지고 있다.
• 마지막 노드는 null pointer를 가진다.
  - [N] -> [N] -> [N] -> [N] -> NULL
• 배열과 비교
  - 연결 리스트는 배열보다 더 유연하다.
  • 연결리스트에 노드를 삽입, 삭제를 쉽게 할 수 있고 리스트를 더 키우거나 줄일 수 있다. 그러나 random access(인덱스로 접근)의 기능을 잃는다. 배열은 어떤 원소에 접근하는 시간(O(1))은 같다. 그러나 연결 리스트의 경우 접근하는 데이터의 노드가 가장 앞에 있을 때 빠르고(O(1)) 가장 뒤에 있을 때 느리다.(O(n))

연결 리스트 구현 (데이터는 int형, 단순 기능들(생성, 삭제, 검색, 추가 등))
linked_list.h

#ifndef LINKED_LIST_H
#define LINKED_LIST_H

struct node {
	int data;
    struct node *next;
}

#include <stdlib.h> // memory allocation

struct node *create_node(int n);
struct node *add_to_list(struct node *list, int n);
void add_to_list(struct node **list, int n); // pointers to pointers
struct node *read_numbers(void);
struct node *search_list(struct node *list, int n);
struct node *delete_from_list(struct node *list, int n);
void delete_from_list(struct node **list, int n); // pointers to pointers
void delete_list(struct node **list);
struct node *insert_into_ordered_list(struct node *list, struct node *new);

#endif

linked_list.c

#include "linked_list.h"

struct node *create_node(int n)
{
	struct node *new;
    if (new == NULL) {
    	printf("Error: malloc failed in create_node\n");
        return NULL;
    }
    new->data = n;
    new->next = NULL;
    
    return new;
}

struct node *add_to_list(struct node *list, int n)
{
	struct node *new_node;
    
    new_node = malloc(sizeof(struct node));
    if (new_node == NULL) {
    	printf("Error: malloc failed in add_to_list\n");
        exit(EXIT_FAILURE);
    }
    new_node->value = n;
    new_node->next = list;
    return new_node;
}

// pointers to pointers
void add_to_list(struct node **list, int n)
{
	struct node *new_node;
    
    new_node = malloc(sizeof(struct node));
    if (new_node == NULL) {
    	printf("Error: malloc failed in add_to_list\n");
        exit(EXIT_FAILURE);
    }
    new_node->value = n;
    new_node->next = *list;
    *list = new_node;
}

struct node *read_numbers(void)
{
	struct node *first = NULL;
    int n;
    
    printf("Enter a series of integers (0 to terminate): ");
    for (;;) {
    	scanf("%d", &n);
        if (n == 0)
        	return first;
        first = add_to_list(first, n);
    }
}

struct node *search_list(struct node *list, int n)
{
	while (list != NULL && list->value != n)
    	list = list->next;
    return list;
}

struct node *delete_from_list(struct node *list, int n)
{
	struct node *cur, *prev;
    
    for (cur = list, prev = NULL;
    	 cur != NULL && cur->value != n;
         prev = cur, cur = cur->next)
    	;
    if (cur == NULL)
    	return list;
    if (prev == NULL)
    	list = list->next;
    else
    	prev->next = cur->next;
    free(cur);
    return list;
}

void delete_from_list(struct node **list, int n)
{
	struct node *temp; // a pointer to the node you delete
    
    if ((*list)->value == n) {
    	temp = *list;
        *list = (*list)->next;
        free(temp);
        return ;
    }
    while ((*list)->next != NULL && (*list)->next->value != n)
    	list = &(*list)->next;
    if ((*list)->next != NULL) {
    	temp = (*list)->next;
        (*list)->next = (*list)->next->next;
        free(temp);
    }
}

void delete_list(struct node **list)
{
	struct node *temp;
    
    if (*list == NULL)
    	return;
    while (*list != NULL) {
    	temp = *list;
        *list = (*list)->next;
        free(temp);
    }
}

struct node *insert_into_ordered_list(struct node *list, struct node *new)
{
	struct node *cur = list, *prev = NULL;
    
    while (cur != NULL && cur->value <= new_node->value) {
    	prev = cur;
        cur = cur->next;
    }
    if (prev == NULL) {
    	new->next = cur;
        list = new;
    } else {
    	new->next = cur;
        prev->next = new;
    }
    return list;
}

몇 가지 실수했던 부분들

• 포인터에 대한 이해도 있어야되지만 범위를 이해하고 있는게 더 중요하다.
  - 먼저 함수의 매개변수도 지역변수이므로 범위를 벗어나면 사라진다. 이 매개변수를 잘 이용하면 된다.
  - 단일 포인터 매개변수도 잘 이용할 수 있다. 어차피 범위를 벗어나면 사라지니 매개변수의 활용이 중요.

  void delete_from_list(struct node **list, int n)
  ...
  	// 아래 while문 안에서 매개변수를 이용해야한다. 아니면 원래 주소(매개변수가 가르키는 주소)의 이동이 발생
  	while ((*list)->next != NULL && (*list)->next->value != n)
  		list = &(*list)->next;
  	if ((*list)->next != NULL) {
  		temp = (*list)->next;
          // 여기서는 본 주소의 이동이 필요
   	   (*list)->next = (*list)->next->next;
   	   free(temp);
  	}
   ...
  

• 루프문 안에서 범위를 이용할 수도 있다. 괄호를 벗어나면 사라진다. 주소를 찍어보면 이해하기 수월하다. 책에서는 전역 포인터 변수를 사용하는 부분이 있는데 그 부분에서 유용했다.

  struct node *delete_node(struct node *list, int n)
  {
  	struct node *temp; // 삭제할 노드를 임시적으로 담을 포인터 변수
      
      for (struct node *p = list; p->next != NULL; p = p->next) {
      	if (p->next->value == n) {
          	temp = p->next;
              p->next = p->next->next;
              free(temp);
              // break; 또는 같은 값을 계속 찾아 지우게 나두면 된다.
          }
      }
      return list; // list의 주소에는 변화가 없다
  }

• 포인터 같은 경우 주소를 일일이 대조해서 찍어보면 이해하는데 무리 없을 것이다.

출처: K.N.KING C PROGRAMMING A MODERN APPROACH