About

This is an implementation of double linked lists for strings in plain C.

Code

stringDoubleLinkedList.c
///////////////////////////////////////////////////////////////////////////
//    Copyright (C) 2015 Wizardry and Steamworks - License: GNU GPLv3    //
///////////////////////////////////////////////////////////////////////////
//                                                                       //
//   stringDoubleLinkedList                                              //
//                                                                       //
//   An implementation of a double linked list of strings.               //
//   Implemented functions:                                              //
//       - insert after                                                  //
//       - insert before                                                 //
//       - is empty                                                      //
//       - count                                                         //
//       - size                                                          //
//       - print                                                         //
//                                                                       //
///////////////////////////////////////////////////////////////////////////
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
/* The stringDoubleLinkedList node structure with prior pointing to the
 * previous element in the double linked list and later pointing to the
 * next element in the double linked list.
 */
typedef struct node {
    char *store;
    struct node *prior, *later;
} stringDoubleLinkedListNode;
 
/*
 * The stringDoubleLinkedList structure with head poiting to the first
 * element in the double linked list and tail pointing to the last element
 * in the doublelinked list.
 */
typedef struct {
    stringDoubleLinkedListNode *head, *tail;
} stringDoubleLinkedList;
 
/*
 * Creates a new stringDoubleLinkedList.
 */
stringDoubleLinkedList* stringDoubleLinkedListCreate(void) {
    stringDoubleLinkedList *l = (stringDoubleLinkedList*)calloc(1, sizeof(stringDoubleLinkedList));
    l->head = (stringDoubleLinkedListNode*)calloc(3, sizeof(stringDoubleLinkedListNode *));
    l->tail = l->head;
    l->tail->prior = NULL;
    l->tail->later = NULL;
    return l;
}
 
/*
 * Returns 1 in case the stringDoubleLinkedList is empty or 0 otherwise.
 */
int stringDoubleLinkedListIsEmpty(stringDoubleLinkedList *l) {
    return l->head->later == l->head->prior && l->head->store == NULL;
}
 
/*
 * Returns the number of elements in stringDoubleLinkedList.
 */
int stringDoubleLinkedListCount(stringDoubleLinkedList *l) {
    int count = 0;
    stringDoubleLinkedListNode *root = l->head;
    while (root != NULL)
        ++count;
    return count;
}
 
/*
 * Prints out the current stringDoubleLinkedList.
 */
void stringDoubleLinkedListPrint(stringDoubleLinkedList *l) {
    stringDoubleLinkedListNode *root;
    if (stringDoubleLinkedListIsEmpty(l)) {
        printf("Linked list is empty.\n");
        return;
    }
    root = l->head;
    printf("Elements in linked list: ");
    while (root != NULL) {
        printf("%s ", root->store);
        root = root->later;
    }
    printf("\n");
}
 
/*
 * Inserts a new element e in the stringDoubleLinkedList l before node n.
 */
void stringDoubleLinkedListInsertBefore(stringDoubleLinkedList *l, stringDoubleLinkedListNode *n, char *e) {
    stringDoubleLinkedListNode *root = l->head;
    stringDoubleLinkedListNode *node;
 
    while (root != NULL && root != n)
        root = root->later;
 
    node = (stringDoubleLinkedListNode*)calloc(3, sizeof(stringDoubleLinkedListNode *));
    node->store = (char*)calloc(strlen(e) + 1, sizeof(char *));
    memcpy(node->store, e, strlen(e) + 1);
 
    if (stringDoubleLinkedListIsEmpty(l)) {
        node->prior = NULL;
        node->later = NULL;
        l->head = node;
        l->tail = node;
        return;
    }
 
    node->later = n;
    if (n->prior != NULL) {
        node->prior = n->prior;
        (n->prior)->later = node;
    }
    n->prior = node;
 
    if (l->head->prior != NULL)
        l->head = l->head->prior;
    if (l->tail->later != NULL)
        l->tail = l->tail->later;
}
 
/*
 * Inserts a new element e in the stringDoubleLinkedList l after node n.
 */
void stringDoubleLinkedListInsertAfter(stringDoubleLinkedList *l, stringDoubleLinkedListNode *n, char *e) {
    stringDoubleLinkedListNode *root = l->head;
    stringDoubleLinkedListNode *node;
 
    while (root != NULL && root != n)
        root = root->later;
 
    node = (stringDoubleLinkedListNode*)calloc(3, sizeof(stringDoubleLinkedListNode *));
    node->store = (char*)calloc(strlen(e) + 1, sizeof(char *));
    memcpy(node->store, e, strlen(e) + 1);
 
    if (stringDoubleLinkedListIsEmpty(l)) {
        node->prior = NULL;
        node->later = NULL;
        l->head = node;
        l->tail = node;
        return;
    }
 
    node->prior = n;
    if (n->later != NULL) {
        node->later = n->later;
        (n->later)->prior = node;
    }
    n->later = node;
 
    if (l->head->prior != NULL)
        l->head = l->head->prior;
    if (l->tail->later != NULL)
        l->tail = l->tail->later;
}
 
/*
 * Deletes node n from the stringDoubleLinkedList l.
 */
void stringDoubleLinkedListDelete(stringDoubleLinkedList *l, stringDoubleLinkedListNode *n) {
    stringDoubleLinkedListNode *root = l->head;
 
    while (root != NULL && root != n)
        root = root->later;
 
    if (root == NULL || root != n)
        return;
 
    if (n->prior == NULL && n->later == NULL) {
        n->store = NULL;
        free(n);
        return;
    }
 
    if (n->prior == NULL) {
        (n->later)->prior = NULL;
        l->head = l->head->later;
        free(n);
        return;
    }
 
    if (n->later == NULL) {
        (n->prior)->later = NULL;
        l->tail = l->tail->prior;
        free(n);
        return;
    }
 
    (n->prior)->later = n->later;
    (n->later)->prior = n->prior;
    free(n);
}
 
int main(void) {
    stringDoubleLinkedList *l = stringDoubleLinkedListCreate();
    //printf("Linked list is empty: %d\n", stringDoubleLinkedListIsEmpty(l));
 
    stringDoubleLinkedListPrint(l);
    stringDoubleLinkedListInsertAfter(l, l->head, "Hello");
    stringDoubleLinkedListPrint(l);
    stringDoubleLinkedListInsertAfter(l, l->head, "World");
    stringDoubleLinkedListPrint(l);
    //printf("head later: %s\n", l->head->later->store);
    stringDoubleLinkedListInsertAfter(l, l->head->later, "DAY");
    stringDoubleLinkedListPrint(l);
    stringDoubleLinkedListInsertAfter(l, l->tail->prior, "final");
    stringDoubleLinkedListPrint(l);
 
    stringDoubleLinkedListDelete(l, l->head);
    stringDoubleLinkedListPrint(l);
 
    stringDoubleLinkedListPrint(l);
    stringDoubleLinkedListInsertBefore(l, l->head, "Hello");
    stringDoubleLinkedListPrint(l);
    stringDoubleLinkedListInsertBefore(l, l->head, "World");
    stringDoubleLinkedListPrint(l);
    //printf("head later: %s\n", l->head->later->store);
    stringDoubleLinkedListInsertBefore(l, l->head->later, "DAY");
    stringDoubleLinkedListPrint(l);
    stringDoubleLinkedListInsertBefore(l, l->tail->prior, "final");
    stringDoubleLinkedListPrint(l);
    return 0;
}

fuss/c/data_structures/linked_lists/double_linked_lists/strings.txt ยท Last modified: 2017/02/22 18:30 (external edit)

Access website using Tor Access website using i2p


For the copyright, license, warranty and privacy terms for the usage of this website please see the license, privacy and plagiarism pages.