リンクリストの練習

LinkedList.c

// -*- mode: c; coding: utf-8 -*-
/*
 * リンクリストの練習
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 * リストの要素型
 */
typedef struct _ListElement {
  struct _ListElement* prev; // 前の要素へのポインタ
  struct _ListElement* next; // 次の要素へのポインタ
  char* data; // データ
} ListElement;

/*
 * リスト型
 */
typedef struct {
  ListElement* first; // 先頭の要素へのポインタ
  ListElement* last; // 末尾の要素へのポインタ
  size_t size; // 要素数
} LinkedList;

/*
 * 新しく要素を作成する
 * @param data_size 作成する要素のデータサイズ
 * @return 作成した要素へのポインタ（エラー時はNULL）
 */
ListElement* newElement(size_t data_size) {
  ListElement* elem = (ListElement*)malloc(sizeof(ListElement));
  if (elem == NULL) {
    return NULL;
  }
  elem->data = (char*)malloc(sizeof(char) * data_size);
  if (elem->data == NULL) {
    free(elem);
    return NULL;
  }
  return elem;
}

/*
 * 新しくリストを作成する
 * @return 作成したリストへのポインタ（エラー時はNULL）
 */
LinkedList* newList() {
  LinkedList* list = (LinkedList*)malloc(sizeof(LinkedList));
  if (list == NULL) {
    return NULL;
  }
  list->first = NULL;
  list->last = NULL;
  list->size = 0;
  return list;
}

/*
 * リストにデータを追加する
 * @param list 対象のリストへのポインタ
 * @param data 追加するデータへのポインタ
 * @param data_size 追加するデータのサイズ
 * @return 成功した場合は0、失敗した場合は-1
 */
int pushElement(LinkedList* list, char* data, size_t data_size) {
  if (list == NULL) {
    return -1;
  }
  ListElement* elem = newElement(data_size);
  if (elem == NULL) {
    return -1;
  }
  void* ret = memcpy(elem->data, data, data_size);
  if (ret == NULL) {
    return -1;
  }

  if (list->first == NULL) {
    list->first = elem;
  }

  if (list->last == NULL) {
    list->last = elem;
  }
  else {
    list->last->next = elem;
    elem->prev = list->last;
    list->last = elem;
  }
  list->size++;
  return 0;
}

/*
 * リストから要素を削除する
 * @param list 対象のリストへのポインタ
 * @param index 削除する要素の番号（0始まり）
 * @return 成功した場合は0、失敗した場合は-1
 */
int deleteElement(LinkedList* list, size_t index) {
  ListElement* elem = list->first;
  size_t i = 0;
  for (i = 0; elem && i < index; i++) {
    elem = elem->next;
  }
  if (elem == NULL) {
    return -1;
  }
  ListElement* prev = elem->prev;
  ListElement* next = elem->next;

  if (prev == NULL) { // 先頭
    list->first = next;
  }
  else {
    prev->next = next;
  }
  if (next == NULL) { // 末尾
    list->last = prev;
  }
  else {
    next->prev = prev;
  }

  free(elem->data);
  free(elem);
  list->size--;
  return 0;
}

/*
 * リストを削除する
 * @param list 対象のリストへのポインタ
 */
void deleteList(LinkedList* list) {
  ListElement* p = list->first;
  ListElement* tmp = NULL;
  while (p) {
    tmp = p;
    p = p->next;
    free(tmp->data);
    free(tmp);
  }
  free(list);
}

void showList(LinkedList* list) {
  ListElement* p = list->first;
  int i = 1;
  while (p) {
    printf("  %d:\t%s\n", i++, p->data);
    p = p->next;
  }
}

void showListBackward(LinkedList* list) {
  ListElement* p = list->last;
  int i = list->size;
  while (p) {
    printf("  %d:\t%s\n", i--, p->data);
    p = p->prev;
  }
}

int main(int argc, char *argv[])
{
  LinkedList* list = newList();
  pushElement(list, "123", 4);
  pushElement(list, "456", 4);
  pushElement(list, "789", 4);
  pushElement(list, "123456", 7);
  pushElement(list, "234567", 7);
  pushElement(list, "345678", 7);
  pushElement(list, "456789", 7);

  puts("Forward:");
  showList(list);
  puts("Backward:");
  showListBackward(list);
  puts("-----");
  puts("** Delete elements **");
  deleteElement(list, 0);
  deleteElement(list, 3);
  deleteElement(list, list->size - 1);
  puts("Forward:");
  showList(list);
  puts("Backward:");
  showListBackward(list);

  deleteList(list);
  return 0;
}