[자료구조] C언어 - 이중 연결 리스트(doubly linked list) 구현 - 객체지향

- C언어로 구현한 리스트 (doubly linked list) 코드이다. 완벽하진 않지만 c에서 객체지향 개념을 넣을 수 있는 기본 베이스는 마련해둔 코드이다.

 

- 글 말고 github으로 보려면 여기를 누르면 된다.

 

- 영어를 잘 못하지만 주석을 영어로 작성했으므로 틀린 표현이 많을 수 있다. (댓글로 알려줘요 ㅠ)

 

0. 사용 예시

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

int main(int argc, char* argv[]) {
	list_t* l = create_list();
	
	printf("--- insert test ---\n");
	l->op->insert_to_head(l, "aaa");
	l->op->insert_to_tail(l, "bbbb");
	l->op->insert_to_head(l, "cc");
	l->op->insert_to_head(l, "dddddd");
	l->op->insert_to_head(l, "eeeeeeee");
	printf("::: %d :::\n", l->op->get_size(l));
	l->op->print(l);

	printf("--- insert before node test ---\n");
	node_t* pos = l->op->get_head_node(l);
	pos = pos->next->next;
	l->op->insert_to_before_node(l, pos, "here");
	printf("::: %d :::\n", l->op->get_size(l));
	l->op->print(l);	
	
	printf("--- delete test ---\n");
	l->op->delete_tail_node(l);
	l->op->delete_head_node(l);
	printf("::: %d :::\n", l->op->get_size(l));
	l->op->print(l);	
	
	l->op->destroy(l);
}

 

1. node.h

/**
* Node structure
* made by nahwasa
*/

#ifndef NODE_H_NAHWASA
#define NODE_H_NAHWASA

typedef struct node {
   struct node* prev;   // previous Node
   struct node* next;   // next Node
   void* data;      // node's data. it can be any data type
} node_t;

#endif

 

2. list.h

/**
* Basic Linked List Header
* This list using node(node.h)
* made by nahwasa
*/

#ifndef BASIC_LIST_H_NAHWASA
#define BASIC_LIST_H_NAHWASA

#include"node.h"

typedef struct list_head {
   node_t* head;   // first Node
   node_t* tail;   // last Node
   int size;   // number of Nodes
   struct list_operations* op;   // list operations
} list_t;

struct list_operations {
   int (*get_size)(list_t* l);
   int (*is_empty)(list_t* l);
   void (*insert_to_head)(list_t* l, void* data); 
   void (*insert_to_tail)(list_t* l, void* data); 
   void (*delete_head_node)(list_t* l); 
   void (*delete_tail_node)(list_t* l); 
   node_t* (*get_head_node)(list_t* l); 
   node_t* (*get_tail_node)(list_t* l);
   void (*print)(list_t* l);
   void (*destroy)(list_t* l);
   void (*insert_to_before_node)(list_t* l, node_t* pos, void* data);
};

extern list_t* create_list();

#endif

 

3. list.c

/**
* Basic Linked List
* made by nahwasa
*/

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

list_t* create_list();
static void destroy(list_t* l);
static int get_size(list_t* l);
static int is_empty(list_t* l);
static void insert_to_head(list_t* l, void* data); 
static void insert_to_tail(list_t* l, void* data); 
static void delete_head_node(list_t* l); 
static void delete_tail_node(list_t* l); 
static void print(list_t* l);
static node_t* get_head_node(list_t* l); 
static node_t* get_tail_node(list_t* l);
static void insert_to_before_node(list_t* l, node_t* pos, void* data);

/*
* Operations can be overriden
* Someone who wants to change the operations can make their own create_list function and change '&op' to another
*/
static struct list_operations op =
   {
      .get_size = get_size,
      .is_empty = is_empty,
      .insert_to_head = insert_to_head,
      .insert_to_tail = insert_to_tail,
      .delete_head_node = delete_head_node,
      .delete_tail_node = delete_tail_node,
      .print = print,
      .get_head_node = get_head_node,
      .get_tail_node = get_tail_node,
      .destroy = destroy,
      .insert_to_before_node = insert_to_before_node
   };


/*
* create list object and return
*/
list_t* create_list()
{   
   list_t* l = (list_t*)malloc(sizeof(list_t));
   
   l->op = &op;
   l->head = l->tail = NULL;
   l->size = 0;

   return l;
}

/*
* c language doesn't provide the way to release memory
* so programmers must provide a destroy function
*/
static void destroy(list_t* l)
{
   node_t* p;
   node_t* t;

   if ( l->op->get_size(l) > 0 ) {
      p = l->op->get_head_node(l);
      while (p != NULL) {         
         t = p->next;
         p->next = p->prev = p->data = NULL;            
         free(p);
         p = t;
      }
      l->head = NULL;
      l->tail = NULL;
      l->size = 0;
      free(l);
      l = NULL;
   }
}

/*
* return the number of Nodes
*/
static int get_size(list_t* l) 
{   
   return l->size;
}

/*
* if list has no node, return true(1)
*/
static int is_empty(list_t* l)
{
   return !l->op->get_size(l);
}

/*
* insert Node to first of list
*/
static void insert_to_head(list_t* l, void* data) 
{   
   node_t* nd = (node_t*)malloc(sizeof(node_t)); 
   
   if ( l->op->is_empty(l) ) {   // when there's no node
      nd->prev = nd->next = NULL;
      nd->data = data;
      l->head = l->tail = nd;
   } else {
      nd->prev = NULL;
      nd->next = l->head;
      nd->data = data;
      l->head->prev = nd;
      l->head = nd;
   }

   l->size++;
}

/*
* insert Node to last of list
*/
static void insert_to_tail(list_t* l, void* data) 
{
   node_t* nd = (node_t*)malloc(sizeof(node_t));

   if ( l->op->is_empty(l) ) {
      nd->prev = nd->next = NULL;
      nd->data = data;
      l->head = l->tail = nd;
   } else {
      nd->next = NULL;
      nd->prev = l->tail;
      nd->data = data;
      (l->tail)->next = nd;
      l->tail = nd;
   }

   l->size++;
}

/*
* insert new Node before 'pos' Node
*/
static void insert_to_before_node(list_t* l, node_t* pos, void* data)
{
   node_t* nd = (node_t*)malloc(sizeof(node_t));

   if ( l->head == pos ) {
      l->op->insert_to_head(l, data);
      return;
   }

   if ( l->op->is_empty(l) ) {
      nd->prev = nd->next = NULL;
      nd->data = data;
      l->head = l->tail = nd;
   } else {
      nd->data = data;
      pos->prev->next = nd;
      nd->next = pos;
      nd->prev = pos->prev;
      pos->prev = nd;         
   }

   l->size++;
}

/*
* delete first Node
*/
static void delete_head_node(list_t* l) 
{
   if ( l->op->get_size(l) <= 1 ) {   // when there's No Node or only one Node
      l->head = l->tail = NULL;
      l->size = 0;
   } else {
      l->head = l->head->next;
      l->head->prev = NULL;
      l->size--;
   }
}

/*
* delete last Node
*/
static void delete_tail_node(list_t* l) 
{
   if (l->op->get_size(l) <= 1) {
      l->head = l->tail = NULL;
      l->size = 0;
   } else {
      l->tail = l->tail->prev;
      l->tail->next = NULL;
      l->size--;
   }
}

/*
* print the Nodes
*/
static void print(list_t* l)
{
   node_t* p = l->op->get_head_node(l);

   while (p != NULL) {
      printf("%s\n", (char*)p->data);
      p = p->next;      
   }
}


static node_t* get_head_node(list_t* l) 
{
   return l->head;
}

static node_t* get_tail_node(list_t* l) 
{
   return l->tail;
}