1 // linkedlist.h
  2 #ifndef __LINKEDLIST_H__
  3 #define __LINKEDLIST_H__
  4 
  5 #include <assert.h>
  6 #include <malloc.h>
  7 #include <string.h>
  8 
  9 typedef int LinkedListData;
 10 
 11 typedef struct LinkedListNode {
 12     LinkedListData data;
 13 
 14     struct LinkedListNode * prior;
 15     struct LinkedListNode * next;
 16 } LinkedListNode, *LinkedList;
 17 
 18 typedef enum {
 19     TRAVELDIR_FORWARD, TRAVELDIR_BACKWARD
 20 } LinkedListTravelDir;
 21 
 22 LinkedList linkedlist_new();
 23 void linkedlist_destory(LinkedList *list);
 24 
 25 void linkedlist_insert(LinkedList list, LinkedListTravelDir dir, int location,
 26         const LinkedListData data);
 27 void linkedlist_delete(LinkedList list, LinkedListTravelDir dir, int location);
 28 int linkedlist_locate(const LinkedList list, LinkedListTravelDir dir,
 29         const LinkedListData data, int (*fpCompare)(const void *, const void *));
 30 LinkedListData * linkedlist_get(LinkedList list, LinkedListTravelDir dir,
 31         int location);
 32 int linkedlist_length(const LinkedList list);
 33 
 34 #endif // __LINKEDLIST_H__
 35 
 36 // linkedlist.c
 37 #include "linkedlist.h"
 38 
 39 LinkedList linkedlist_new() {
 40     // alloc head node
 41     LinkedList list = malloc(sizeof(LinkedListNode));
 42     assert(list);
 43 
 44     // initialize head node‘s pointer field
 45     list->prior = list;
 46     list->next = list;
 47 
 48     return list;
 49 }
 50 
 51 void linkedlist_destory(LinkedList *list) {
 52     while (linkedlist_length(*list)) {
 53         linkedlist_delete(*list, TRAVELDIR_FORWARD, 1);
 54     }
 55     free (*list);
 56     *list = NULL;
 57 }
 58 
 59 void linkedlist_insert(LinkedList list, LinkedListTravelDir dir, int location,
 60         const LinkedListData data) {
 61     LinkedList pCurNode = list;
 62     assert(location > 0 && location <= linkedlist_length(list) + 1);
 63 
 64     // alloc new node
 65     LinkedListNode * pNode = malloc(sizeof(LinkedListNode));
 66     assert(pNode);
 67     memcpy(&(pNode->data), &data, sizeof(LinkedListData));
 68 
 69     // move current pointer to prior node
 70     if (dir == TRAVELDIR_FORWARD) {
 71         for (int i = 0; i < location - 1; i++, pCurNode = pCurNode->next)
 72             ;
 73 
 74     } else {
 75         if (dir == TRAVELDIR_BACKWARD) {
 76             for (int i = 0; i < location; i++, pCurNode = pCurNode->prior)
 77                 ;
 78         }
 79     }
 80 
 81     // insert new node
 82     pNode->next = pCurNode->next;
 83     pNode->prior = pCurNode;
 84     pCurNode->next = pNode;
 85     pNode->next->prior = pNode;
 86 }
 87 
 88 void linkedlist_delete(LinkedList list, LinkedListTravelDir dir, int location) {
 89     LinkedList pCurNode = list;
 90     assert(location > 0 && location < linkedlist_length(list) + 1);
 91 
 92     // move current pointer to the node will deleted
 93     if (dir == TRAVELDIR_FORWARD) {
 94         for (int i = 0; i < location; i++, pCurNode = pCurNode->next)
 95             ;
 96     } else {
 97         if (dir == TRAVELDIR_BACKWARD) {
 98             for (int i = 0; i < location; i++, pCurNode = pCurNode->prior)
 99                 ;
100         }
101     }
102 
103     // delete current node
104     pCurNode->prior->next = pCurNode->next;
105     pCurNode->next->prior = pCurNode->prior;
106     free(pCurNode);
107 }
108 
109 int linkedlist_locate(const LinkedList list, LinkedListTravelDir dir,
110         const LinkedListData data, int (*fpCompare)(const void *, const void *)) {
111     static int location = 0;
112     static LinkedList pCurNode = NULL;
113 
114     // if list argument is NULL, continue to start locate
115     if (list) {
116         location = 1;
117         pCurNode = list->next;
118     }
119     assert(location && pCurNode);
120 
121     // locate data
122     while (pCurNode != list) {
123         if (!fpCompare(&(pCurNode->data), &data)) {
124             return location;
125         }
126         location++;
127         if (dir == TRAVELDIR_FORWARD) {
128             pCurNode = pCurNode->next;
129         } else {
130             if (dir == TRAVELDIR_BACKWARD) {
131                 pCurNode = pCurNode->prior;
132             }
133         }
134     }
135 
136     return -1;
137 }
138 
139 LinkedListData * linkedlist_get(LinkedList list, LinkedListTravelDir dir,
140         int location) {
141     LinkedList pCurNode = list;
142     assert(location > 0 && location < linkedlist_length(list) + 1);
143 
144     // move pointer to the node wanna get
145     if (dir == TRAVELDIR_FORWARD) {
146         for (int i = 0; i < location; i++, pCurNode = pCurNode->next)
147             ;
148     } else {
149         if (dir == TRAVELDIR_BACKWARD) {
150             for (int i = 0; i < location; i++, pCurNode = pCurNode->prior)
151                 ;
152         }
153     }
154 
155     return &(pCurNode->data);
156 }
157 
158 int linkedlist_length(const LinkedList list) {
159     int length = 0;
160     assert(list);
161     LinkedList pCurNode = list->next;
162 
163     while (pCurNode != list) {
164         length++;
165         pCurNode = pCurNode->next;
166     }
167 
168     return length;
169 }