About

This implementation uses Amiga OS types and memory-allocation semantics in order to be used for other programs that rely on a double linked list implementation.

The program can be compiled on the Amiga using SAS/C by issuing:

sc link doubleLinkedList.c

When the program is run, it will perform a series of operations using the implemented double linked list functions and display the output in the calling shell:

Head: Good day!
Tail: hi...
nnp: Hello there!
Head: Good day!
Elements in the linked list: Good day! STOP Hello there! hi... 
Head: STOP
Elements in the linked list: STOP Hello there! hi... 
Count: 3
Elements in the linked list: STOP Hello there! START hi... 
Elements in the linked list: Hello there! START hi... 
Elements in the linked list: Hello there! TEST START hi... 

Code

doubleLinkedList.c
/*************************************************************************/
/*    Copyright (C) 2015 Wizardry and Steamworks - License: GNU GPLv3    */
/*************************************************************************/
/*                                                                       */
/*  doubleLinkedList                                                     */
/*                                                                       */
/*  An implementation of linked lists for Amiga OS.                      */
/*                                                                       */
/*  Implemented functions:                                               */
/*      - append                                                         */
/*      - insert after                                                   */
/*      - insert before                                                  */
/*      - insert at index                                                */
/*      - element at index                                               */
/*      - remove                                                         */
/*      - remove at index                                                */
/*      - size                                                           */
/*      - is empty                                                       */
/*      - print                                                          */
/*                                                                       */
/*  Compile on Amiga OS using SAS/C: sc link doubleLinkedList.c          */
/*                                                                       */
/*************************************************************************/
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#include <proto/exec.h>
#include <proto/dos.h>
 
/* The linked list element structure with storage containing pointers to
 * the next, respectively the previous element.
 */
typedef struct doubleLinkedListElement doubleLinkedListElement;
typedef struct doubleLinkedListElement {
    UBYTE *store;
    doubleLinkedListElement *nextElement;
    doubleLinkedListElement *prevElement;
};
 
/* The double linked list structure holding the size of the linked list
 * with pointers to both the head and the tail of the linked list.
 */
typedef struct {
    ULONG size;
    doubleLinkedListElement *head;
    doubleLinkedListElement *tail;
} doubleLinkedList;
 
/* Creates a double linked list. */
doubleLinkedList *doubleLinkedListCreate(void) {
    doubleLinkedList *l = (doubleLinkedList *)AllocMem(
        sizeof(doubleLinkedList),
        MEMF_ANY|MEMF_CLEAR
    );
    l->head = NULL;
    l->tail = NULL;
    l->size = 0;
    return l;
}
 
/* Creates a double linked list. */
doubleLinkedListElement *doubleLinkedListElementCreate(UBYTE *data) {
    doubleLinkedListElement *e = (doubleLinkedListElement *)AllocMem(
        sizeof(doubleLinkedListElement),
        MEMF_ANY|MEMF_CLEAR
    );
    e->store = (UBYTE *)AllocMem(
        strlen(data) * sizeof(UBYTE *) + 1,
        MEMF_ANY|MEMF_CLEAR
    );
    CopyMem(data, e->store, strlen(data) * sizeof(UBYTE *) + 1);
    e->prevElement = NULL;
    e->nextElement = NULL;
    return e;
}
 
/* Appends an element to the end of the double linked list. */
doubleLinkedListElement *doubleLinkedListAppend(doubleLinkedList *l, doubleLinkedListElement *e) {
    /* Update the element. */
    e->prevElement = l->tail != NULL ? l->tail : NULL;
    e->nextElement = NULL;
    /* Update head and tail list pointers. */
    switch(l->head != NULL) {
        case FALSE:
            l->head = e;
            break;
    }
    switch(l->tail != NULL) {
        case TRUE:
            l->tail->nextElement = e;
        default:
            l->tail = e;
            break;
    }
    ++l->size;
    return e;
}
 
/* Inserts a double linked list element after an element. */
doubleLinkedListElement *doubleLinkedListInsertNext(
    doubleLinkedList *l, doubleLinkedListElement *e, doubleLinkedListElement *a) {
    a->nextElement = e->nextElement;
    if(a->nextElement != NULL)
        a->nextElement->prevElement = a;
    a->prevElement = e;
    e->nextElement = a;
    if(a->nextElement == NULL)
        l->tail = a;
    ++l->size;
    return a;
}
 
/* Inserts a double linked list element before an element. */
doubleLinkedListElement *doubleLinkedListInsertPrev(
    doubleLinkedList *l, doubleLinkedListElement *e, doubleLinkedListElement *a) {
    a->nextElement = e;
    a->prevElement = e->prevElement;
    if(e->prevElement != NULL)
        e->prevElement->nextElement = a;
    e->prevElement = a;
    if(a->prevElement == NULL)
        l->head = a;
    ++l->size;
    return a;
}
 
/* Returns the element at a given index. */
doubleLinkedListElement *doubleLinkedListElementAtIndex(doubleLinkedList *l, ULONG i) {
    doubleLinkedListElement *e = l->head;
    while(i > 0) {
        e = e->nextElement;
        --i;
    }
    return e;
}
 
/* Inserts a double linked list element at a given index. */
doubleLinkedListElement *doubleLinkedListInsertAt(
    doubleLinkedList *l, doubleLinkedListElement *a, ULONG i) {
    return doubleLinkedListInsertPrev(l, doubleLinkedListElementAtIndex(l, i), a);
}
 
/* Removes a double linked list element. */
void doubleLinkedListRemove(doubleLinkedList *l, doubleLinkedListElement *e) {
    if(e->prevElement != NULL)
        e->prevElement->nextElement = e->nextElement;
    if(e->nextElement != NULL)
        e->nextElement->prevElement = e->prevElement;
    if(l->head == e)
        l->head = e->nextElement;
    if(l->tail == e)
        l->tail = e->prevElement;
    --l->size;
}
 
/* Removes a double linked list element at a given index. */
void doubleLinkedListRemoveAt(doubleLinkedList *l, ULONG i) {
    doubleLinkedListRemove(l, doubleLinkedListElementAtIndex(l, i));
}
 
/* Returns true if the double linked list is empty. */
BOOL doubleLinkedListIsEmpty(doubleLinkedList *l) {
    return (BOOL)(l->head == l->tail);
}
 
/* Returns the number of elements in the double-linked list. */
ULONG doubleLinkedListSize(doubleLinkedList *l) {
    return l->size;
}
 
/* Prints the double linked list. */
void doubleLinkedListPrint(doubleLinkedList *l) {
    doubleLinkedListElement *e;
    if(doubleLinkedListIsEmpty(l)) {
        Printf("List is empty.\n");
        return;
    }
    Printf("Elements in the linked list: ");
    e = l->head;
    do {
        Printf("%s ", e->store);
        e = e->nextElement;
    } while(e != NULL);
    Printf("\n");
}
 
int main(void) {
    doubleLinkedList *l = doubleLinkedListCreate();
    doubleLinkedListElement *s, *e;
    s = doubleLinkedListElementCreate("Good day!");
    doubleLinkedListAppend(l, s);
    doubleLinkedListAppend(l, doubleLinkedListElementCreate("Hello there!"));
    e = doubleLinkedListElementCreate("hi...");
    doubleLinkedListAppend(l, e);
    Printf("Head: %s\n", l->head->store);
    Printf("Tail: %s\n", l->tail->store);
    Printf("nnp: %s\n", s->nextElement->nextElement->prevElement->store);
    doubleLinkedListInsertNext(l, l->head, doubleLinkedListElementCreate("STOP"));
    Printf("Head: %s\n", l->head->store);
    doubleLinkedListPrint(l);
    doubleLinkedListRemove(l, l->head);
    Printf("Head: %s\n", l->head->store);
    doubleLinkedListPrint(l);
    Printf("Count: %ld\n", doubleLinkedListSize(l));
    doubleLinkedListInsertPrev(l, l->tail, doubleLinkedListElementCreate("START"));
    doubleLinkedListPrint(l);
    doubleLinkedListRemoveAt(l, 0);
    doubleLinkedListPrint(l);
    doubleLinkedListInsertAt(l, doubleLinkedListElementCreate("TEST"), 1);
    doubleLinkedListPrint(l);
}

amiga/development/data_structures/linked_lists/double_linked_list/string.txt ยท Last modified: 2022/04/19 08:28 by 127.0.0.1

Access website using Tor Access website using i2p Wizardry and Steamworks PGP Key


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