정상우
hELLO.
정상우
전체 방문자
382,747
오늘
81
어제
709
  • hELLO. (121)
    • 컴퓨터과학 (4)
      • 알고리즘 & 자료구조 (4)
    • 언어 & 프레임워크 (63)
      • Go (23)
      • PHP & Laravel (40)
    • 웹 (7)
    • 블록체인 (12)
      • 메인넷 (9)
      • 암호화폐 플랫폼 (3)
    • 포트폴리오 (10)
    • 칼럼 (20)
      • 에세이 (4)
      • 개발자스럽게 살기 (14)
      • 회고 (2)
    • 티스토리 (5)

블로그 메뉴

  • ⚡ 개발자 이력서
  • 🌟 깃허브
  • 💻 강의
  • ✨ 예제코드
  • ⭐ 브런치
  • 태그 클라우드
  • 방명록

공지사항

  • 2차 도메인을 설정했습니다 ✨

인기 글

  • JWT(JSON Web Token)의 개념부⋯
    2021.07.29
    JWT(JSON Web Token)의 개념부⋯
  • 'REST' 를 보다 'RESTful' 하게⋯
    2021.08.14
    'REST' 를 보다 'RESTful' 하게⋯
  • [Laravel] 라라벨 프레임워크⋯
    2021.06.10
    [Laravel] 라라벨 프레임워크⋯
  • 깃허브를 포트폴리오로 쓰려면⋯
    2021.12.25
    깃허브를 포트폴리오로 쓰려면⋯
  • 암호화폐 트레이딩 봇을 만들었⋯
    2021.05.12
    암호화폐 트레이딩 봇을 만들었⋯

태그

  • go
  • 프로그래머스
  • 포트폴리오
  • 개발
  • 코딩테스트
  • 블록체인
  • php
  • 라라벨
  • 개발 리뷰
  • Algorithm

최근 댓글

  • 고맙습니다 ~^^
    정상우
  • 오늘 블로그 만들었는데 검색하⋯
    엥뿌삐
  • 좋은 스킨 정말 감사드립니다.⋯
    이태홍
  • 고맙습니다 ㅎㅎ
    정상우
  • 제가 원하던 최고의 스킨입니다⋯
    _HEON

최근 글

  • 빠르게 성장하는 개발자의 세⋯
    2022.06.08
    빠르게 성장하는 개발자의 세⋯
  • 개발자와 엔지니어, 그 사이에서
    2022.05.10
    개발자와 엔지니어, 그 사이에서
  • 아임포트(Iamport)로 결제기능⋯
    2022.04.03
    아임포트(Iamport)로 결제기능⋯
  • 아임포트(Iamport)로 결제기능⋯
    2022.04.01
    아임포트(Iamport)로 결제기능⋯
  • [Laravel] 카페24 호스팅에 라⋯
    2022.03.29
    [Laravel] 카페24 호스팅에 라⋯

티스토리

hELLO · Designed By 정상우.
정상우

hELLO.

C언어로 자료구조 만들기 - 링크드 리스트(Linked List)
컴퓨터과학/알고리즘 & 자료구조

C언어로 자료구조 만들기 - 링크드 리스트(Linked List)

2020. 11. 7. 14:11

이번에는 지난 포스트에 이어서 C언어로 자료구조를 구현해볼 텐데, 이번에는 링크드 리스트다. 양 옆으로 삽입과 삭제가 가능한 양방향 링크드 리스트를 구현하고, 또한 중간에 데이터를 삽입과 삭제가 가능하도록 만든다.

링크드 리스트(Linked List)

링크드 리스트는 정적 배열과 데크와는 다르게 주소값을 서로 연결하여 구성되어 있다. 따라서 메모리 공간이 연속으로 구성되어 있지는 않으며 독립적으로 구성하되, 대신 다음과 이전 주소를 노드에 저장하여 다음 노드와 이전 노드에 접근할 수 있도록 논리적으로 연결된 구조로 표현한다. 

 

Node.h

링크드 리스트에는 노드가 필요하다. 배열처럼 인덱싱을 통해 바로 값을 넣지 않는다. 노드에는 값, 이전 노드의 주소값, 다음 노드의 주소값이 들어가며 이는 구조체로 표현한다.

 

create_node() 함수를 통해 노드를 생성하고 돌려줄 수 있다. 이 함수는 링크드 리스트를 포함한 여러 자료구조에서 사용할 것이다.

typedef struct __Node__ Node;

typedef struct __Node__ {
  Node* prev;
  void* element;
  Node* next;
} Node;

Node* create_node(void*);

/**
 * Create a Node
 *
 * @public
 */
Node* create_node(void* element) {
  Node* node = (Node*) malloc(sizeof(Node));
  node->next = NULL;
  node->element = element;
  node->prev = NULL;

  return node;
}

List

정적 배열 및 데크처럼 가변인자를 통해 데이터를 받을 수 있다. 그러나 이 녀석의 사이즈는 배열의 사이즈와는 다르며 자료구조의 논리적 길이의 불과하다. 값을 넣을 때는 아래에서 언급하게 될 ls_push_back() 함수를 사용한다.

typedef struct __List__ {
  size_t length;

  Node* front;
  Node* back;
} List;

List list(size_t size, ...);

/**
 * Create Linked List
 *
 * @public
 */
List list(size_t size, ...) {
  List ls = { .length = 0, .front = NULL, .back = NULL };
  va_list ap;
  va_start(ap, size);
  for (int i = 0; i < size; i++) {
    ls_push_back(&ls, va_arg(ap, void*));
  }
  va_end(ap);
  return ls;
}

ls_*

링크드 리스트를 위해 구현하게 될 함수는 다음과 같으며 모든 함수를 다 살펴본다. 다음 자료구조는 큐, 스택인데 그것은 링크드 리스트를 기반으로 만들 것이기 때문에 그만큼 분량이 줄어든다. 앞, 뒤, 특정 위치에 값을 넣고 삭제, 반복자로 순회할 수 있고, 링크드 리스트를 비울 수 있다.

void  ls_push_front(List*, void*);
void  ls_pop_front(List*);
void  ls_push_back(List*, void*);
void  ls_pop_back(List*);

void  ls_insert(List*, Node*, void*);
void  ls_erase(List*, Node*);

Node* ls_at(List*, void*);
void  ls_clear(List*);

Node* ls_begin(List*);
Node* ls_end(List*);
Node* ls_next(Node*);
Node* ls_prev(Node*);

int   ls_done(Node*);

ls_push_front(List*, void*), ls_pop_front(List*, void*)

링크드 리스트의 제일 앞에 값을 추가하고 삭제한다. 제일 앞에 값을 추가하는 행위는 노드를 하나 생성하고, 기존의 제일 앞에 있던 노드의 주소값을 현재 추가할 노드의 next 에 추가하고, 기존의 노드의 prev 에 새로 추가할 노드의 주소값을 넣어주면 된다. 그러니까 코드를 보자. 리스트가 비어있는 상태라면 뒤에 노드를 추가한다.

 

/**
 * Push new node at Front
 *
 * @public
 */
void ls_push_front(List* list, void* element) {
  Node* node = create_node(element);
  if (list->front != NULL) {
    node->next = list->front;
    node->prev = NULL;
    list->front->prev = node;
  } else if (list->front == NULL && list->back == NULL) {
    list->back = node;
  }
  list->front = node;
  list->length++;
}

/**
 * Remove node at Front
 *
 * @public
 */
void ls_pop_front(List* list) {
  Node* node = list->front;
  if (list->front->next != NULL) {
    list->front = list->front->next;
    list->front->prev = NULL;
  } else {
    list->back = NULL; list->front = NULL;
  }
  free(node);
  list->length--;
}

값을 삭제하는 상황에서는 노드를 생성하는 것이 아니므로 맨 앞의 노드를 가져온다. 삭제하려는 노드의 다음이 존재한다면 front 를 해당 노드와 변경하고 prev 값을 NULL 로 변경한다. 만약에 노드가 하나 뿐이라면 값을 NULL 로 초기화하고 메모리를 해제한다.

 

데크랑 비교해보라. 데크보다 코드의 길이는 길지만, 연산의 횟수가 다르다. 즉, 링크드 리스트는 데이터의 삽입과 삭제에서 배열 기반 자료구조보다 탁월한 성능을 보인다.

ls_push_back(List*, void*), ls_pop_back(List*, void*)

링크드 리스트의 뒤에서 작업을 하기 위해서 할 일도 사실 앞에서 하는 것과 유사하다. 차이가 있다면 front 에서 처리하던 것을 back 에서 처리한다는 점이다.

 

값을 추가하는 상황에서 기존의 리스트에 노드가 있다면 그 노드는 현재 생성한 노드의 이전 노드가 될 것이므로 포인터를 수정한다. 기존 노드의 다음 노드로 생성한 노드를 지정하고, 마지막으로 링크드 리스트의 마지막 노드를 생성한 노드로 바꿔준다.

/**
 * Push new node at Back
 *
 * @public
 */
void ls_push_back(List* list, void* element) {
  Node* node = create_node(element);
  if (list->back != NULL) {
    node->prev = list->back;
    node->next = NULL;
    list->back->next = node;
  } else if (list->front == NULL && list->back == NULL) {
    list->front = node;
  }
  list->back = node;
  list->length++;
}

/**
 * Remove node at Back
 *
 * @public
 */
void ls_pop_back(List* list) {
  Node* node = list->back;
  if (list->back->prev != NULL) {
    list->back = list->back->prev;
    list->back->next = NULL;
  } else {
    list->back = NULL; list->front = NULL;
  }
  free(node);
  list->length--;
}

값을 삭제할 때는 맨 뒤의 노드를 얻어오고, 기존 리스트의 맨 뒤의 노드를 더 이전의 노드로 변경한뒤, 가져왔던 노드의 메모리를 해제한다.

 

ls_insert(List*, Node*, void*), ls_erase(List*, Node*)

링크드 리스트에서 삽입과 삭제를 할 떄 살펴봐야 할 점은, 특정 위치를 지우는 것이 아니라, 특정 노드를 지우는 것이다. 메모리의 주소 자체는 독립적으로 존재하고 있으므로 위치를 특정하여 지우는 것을 할 수 없다. 즉, 배열처럼 인덱싱을 해서 다이렉트로 접근할 수는 없다.

 

하지만 삽입과 삭제를 할 때 링크드 리스트의 장점이 발휘되는데, 바로 연결된 포인터만 바꿔주면 아주 간편하다는 점이다. 앞과 뒤가 아닌 중간에서 삽입과 삭제를 하더라도 포인터랑 바꿔주면 된다.

/**
 * Insert new node at before the node
 *
 * @public
 */
void ls_insert(List* list, Node* iter, void* element) {
  if (iter == list->front) {
    ls_push_front(list, element);
  } else {
    Node* node = create_node(element);

    node->prev = iter->prev;
    node->next = iter;
    iter->prev->next = node;
    iter->prev = node;
    list->length++;
  }
}

/**
 * Remove node
 *
 * @public
 */
void ls_erase(List* list, Node* iter) {
  if (iter == list->front) {
    ls_pop_front(list);
  } else if (iter == list->back) {
    ls_pop_back(list);
  } else {
    iter->prev->next = iter->next;
    iter->next->prev = iter->prev;

    free(iter);
    list->length--;
  }
}

링크드 리스트에 데이터를 넣을 때, 현재 노드의 앞쪽에 넣는데 iter 파라매터는 바로 뒤의 노드를 지정한다. 링크드 리스트의 맨 앞의 노드와 넣으려는 노드가 동일 한 경우, 맨 앞에 노드를 새로 생성해서 넣어주고, 그렇지 않은 경우 노드를 새로 생성하여 iter 의 앞 쪽에 넣는다.

 

값을 삭제할 때는 파라매터로 넘어오는 노드를 삭제하게 된다. 맨 앞과 맨 뒤라면 ls_pop_front(), ls_pop_back() 등으로 처리하고 그렇지 않다면 포인터를 바꿔주고 메모리를 해제한다.

ls_clear(List*)

이 함수는 링크드 리스트를 비운다. 맨 앞에서 비워도 되고 맨 뒤에서부터 비워도 된다. 중요한 것은 모든 노드의 메모리가 해제되어야 한다는 점이다.

/**
 * Clear Linked List
 *
 * @public
 */
void ls_clear(List* list) {
  size_t s = list->length;
  for (size_t i = 0; i < s; i++) {
    ls_pop_back(list);
  }
}

ls_begin(List*), ls_next(List*), ls_end(List*), ls_prev(List*), ls_done(Node*)

리스트의 반복자의 구현은 다음과 같다. 함수는 많지만 내용이 아주 간단해서 설명이 필요없을 정도다.

/**
 * Get front node
 *
 * @public
 */
Node* ls_begin(List* list) {
  return list->front;
}

/**
 * Get next node
 *
 * @public
 */
Node* ls_next(Node* iter) {
  return iter->next;
}

/**
 * Get back node
 *
 * @public
 */
Node* ls_end(List* list) {
  return list->back;
}

/**
 * Get prev node
 *
 * @public
 */
Node* ls_prev(Node* iter) {
  return iter->prev;
}

/**
 * is Done
 *
 * @public
 */
int ls_done(Node* iter) {
  if (iter == NULL) {
    return 1;
  }
  return 0;
}

ls_at(void*)

링크드 리스트에서 특정 값을 가진 노드를 찾는다. 반복자를 먼저 소개한 이유는, 여기서 반복자를 사용하여 노드를 검색하기 때문이다. 배열기반과 차이점이 보이는가? 배열은 그냥 인덱스로 접근하면 되지만 링크드 리스트는 순차 탐색하여 하나하나 검증한다. 그래서 링크드 리스트는 검색이 느리다.

/**
 * Get node with element
 *
 * @public
 */
Node* ls_at(List* list, void* element) {
  for (Node* iter = ls_begin(list); 1 != ls_done(iter); iter = ls_next(iter)) {
    if (iter->element == element) {
      return iter;
    }
  }
  return NULL;
}

어떻게 사용해볼까?

링크드 리스트의 사용하는 방법 그 자체는 단순하기 때문에 값을 추가해서 반복자로 돌며 마지막에는 노드를 전부 정리하는 예제로 포스트를 마무리한다.

List ls = list(1, "Hello, world!");
ls_push_front(&ls, "Example");

for (Node* iter = ls_begin(&ls); 1 != ls_done(iter); iter = ls_next(iter)) {
  // Example
  // Hello, world!
  printf("%s", (const char*) iter->element);
}

ls_clear(&ls);

더 읽을거리

C언어로 자료구조 만들기 - 트리(BST, Binary Search Tree)

C언어로 자료구조 만들기 - 큐(Queue), 스택(Stack)

C언어로 자료구조 만들기 - 정적 배열(Fixed Array), 데크(Deque)

    '컴퓨터과학/알고리즘 & 자료구조' 카테고리의 다른 글
    • C언어로 자료구조 만들기 - 트리(BST, Binary Search Tree)
    • C언어로 자료구조 만들기 - 큐(Queue), 스택(Stack)
    • C언어로 자료구조 만들기 - 정적 배열(Fixed Array), 데크(Deque)
    C, 개발, 개발 리뷰, 링크드 리스트, 자료구조, 포트폴리오
    정상우
    정상우
    과거의 배움으로 현재를 바꾸고 미래를 만듭니다. #25+2살 #INFJ #개발자 #브런치작가
    댓글쓰기
    1. 2st
      2022.03.28 17:24 신고
      마지막 실행 예제 반복조건이 iter->next !=NULL 이라서 list->back인 경우에 element가 출력이 안되네요.
      그냥 iter !=NULL 로 해주니까 마지막 연결리스트의 element까지 출력됩니다. 좋은 포스팅 감사드립니다!
      수정/삭제댓글쓰기댓글보기
    다음 글
    C언어로 자료구조 만들기 - 큐(Queue), 스택(Stack)
    이전 글
    C언어로 자료구조 만들기 - 정적 배열(Fixed Array), 데크(Deque)
    • 이전
    • 1
    • ···
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • ···
    • 121
    • 다음

    티스토리툴바