Yama Habib's Webpage
C Source Code Example: DoublyLinkedList
Header File
Test Class
The following is an interactive HTML version of the source code for my DoublyLinkedList program
/*
* DoublyLinkedList - A doubly linked list to contain values of type E which
* can be cast from any other primitive type.
*
* Author: Yama H
* Version: 1.2
* Revision: 2.24.2009
*/
#include <stdlib.h>
#include <string.h>
/*
* E's are long doubles because they allocate the most space of all primitive
* types, therefore ensuring enough space for any other type that could be
* cast into it.
*/
typedef long double E;
/*
* A DLLNode (DoublyLinkedListNode) consists of a piece of data of type E
* (which is really usually some other type cast into an E, and can also be a
* pointer) and pointers to the next and previous DLLNodes in the list (NULL
* if the node is a head or tail node.
*/
typedef struct
{
E data;
void* next;
void* prev;
}DLLNode;
/*
* A DoublyLinkedList is just a head Node, a pointer to a tail node, and an int
* representing the amount of elements in the list. The head node is not a
* pointer because it's value never changes unless the list is emptied.
*/
typedef struct
{
DLLNode head; // the head isn't a pointer, but the tail is,
DLLNode* tail; // because the head is static and the tail is dynamic
int elements;
}DoublyLinkedList;
/*
* Initializes List and creates first node.
*/
void DoublyLinkedList_initialize(DoublyLinkedList* dll, E data)
{
if(dll == NULL) return;
(*dll).elements = 1;
(*dll).head.data = data;
(*dll).head.prev = NULL;
(*dll).head.next = NULL;
(*dll).tail = &(*dll).head;
}
/*
* Initializes an empty List.
*/
void DoublyLinkedList_init(DoublyLinkedList* dll)
{
if(dll == NULL) return;
(*dll).elements = 0;
(*dll).head.data = (E)0;
(*dll).head.prev = NULL;
(*dll).head.next = NULL;
(*dll).tail = &(*dll).head;
}
/*
* Adds an entry to the List.
*/
void DoublyLinkedList_addEntry(DoublyLinkedList* dll, E data)
{
if(dll == NULL) return;
if((*dll).elements == 0)
DoublyLinkedList_initialize(dll, data);
else if((*dll).elements == 1)
{
(*dll).tail = malloc(sizeof(DLLNode));
(*(*dll).tail).data = data;
(*(*dll).tail).prev = &(*dll).head;
(*(*dll).tail).next = NULL;
(*dll).head.next = (*dll).tail;
(*dll).elements++;
}
else
{
(*(*dll).tail).next = malloc(sizeof(DLLNode));
(*(DLLNode*)(*(*dll).tail).next).data = data;
(*(DLLNode*)(*(*dll).tail).next).prev = (*dll).tail;
(*(DLLNode*)(*(*dll).tail).next).next = NULL;
(*dll).tail = (DLLNode*)((*(*dll).tail).next);
(*dll).elements++;
}
return;
}
/*
* Removes an entry from the list. Nonzero if list is empty.
*/
int DoublyLinkedList_removeEntry(DoublyLinkedList* dll)
{
if(dll == NULL) return 1;
if((*dll).elements == 0)
return 1;
if((*(*dll).tail).prev == NULL || (*dll).elements == 1)
{
DoublyLinkedList_init(dll);
return 0;
}
(*dll).tail = (DLLNode*)(*(*dll).tail).prev;
free((*(*dll).tail).next);
(*(*dll).tail).next = NULL;
(*dll).elements--;
return 0;
}
/*
* Retrieves the head node. Returns allocated memory if dll is null.
*/
DLLNode DoublyLinkedList_getHead(DoublyLinkedList* dll)
{
if(dll == NULL) return *((DLLNode*)malloc(sizeof(DLLNode)));
return (*dll).head;
}
/*
* Retrieves the tail node. Returns allocated memory if dll is null.
*/
DLLNode DoublyLinkedList_getTail(DoublyLinkedList* dll)
{
if(dll == NULL) return *((DLLNode*)malloc(sizeof(DLLNode)));
return *(*dll).tail;
}
/*
* Retrives the node after the current node. Returns the parameter if the
* current node is the last entry (the tail).
*/
DLLNode DoublyLinkedList_getNext(DLLNode node)
{
if(node.next == NULL)
{
return node;
}
return *((DLLNode*)node.next);
}
/*
* Retrieves the node before the current node. Returns the parameter if the
* current node is the first entry (the head).
*/
DLLNode DoublyLinkedList_getPrev(DLLNode node)
{
if(node.prev == NULL)
return node;
return *((DLLNode*)node.prev);
}
/*
* Retrieves the data from the node passed.
*/
E DoublyLinkedList_getData(DLLNode node)
{
return node.data;
}
/*
* Sets the data in a specified node in the list to a specified value, and
* updates the node passed in. Nonzero on failure.
*/
int DoublyLinkedList_setData(DoublyLinkedList* dll, DLLNode* node, E data)
{
if(dll == NULL) return 1;
if((*dll).elements == 0 || ((*node).next == NULL &&
(*node).prev == NULL && (*dll).elements != 1))
return 1;
if((*node).next == NULL && (*node).prev == NULL &&
(*dll).elements == 1)
{
(*dll).head.data = data;
*node = (*dll).head;
return 0;
}
// we're assuming that the parameter is a pointer to a copy of the node,
// so we do this, just to be safe.
DLLNode* ptr;
if((*node).next == NULL)
{
ptr = (*(DLLNode*)((DLLNode*)(*node).prev)).next;
(*ptr).data = data;
*node = *ptr;
return 0;
}
ptr = (*(DLLNode*)((DLLNode*)(*node).next)).prev;
(*ptr).data = data;
*node = *ptr;
return 0;
}
/*
* Returns 1 if node1 is identical to node2 and 0 if not.
*/
int DoublyLinkedList_equals(DLLNode node1, DLLNode node2)
{
if(node1.data == node2.data && node1.next == node2.next &&
node1.prev == node2.prev)
return 1;
return 0;
}
/*
* Returns the number of elements currently in the list.
*/
int DoublyLinkedList_getElements(DoublyLinkedList* dll)
{
if(dll == NULL) return 0;
return (*dll).elements;
}