Problem with linked list ADT and incomplete structure
Hi,
I am having trouble with a linked list ADT implemtation that uses incomplete structures ie pointers to structures. The code for this ADT was provided for us and I can't get it to work/compile. The assignment was to use the provided ADT to manipulate linked lists. I have created another linked list ADT's that works but doesn't use incomplete structures. It is being very difficult to explore this usage when the provided code doesn't work.
Below is the code that was provided to us as a working example but it doesn't :(
Any help with what is wrong with the code or other examples of similar implementaions would be greatly appreciated.
Code:
// list.h - Linked List ADT
#ifndef _LIST_H_
#define _LIST_H_
struct List;
typedef struct ListNode *Position;
List *ListConstruct(); // NULL if fails
void ListDestroy(List *l);
bool ListEmpty(const List *l);
Position ListHead(const List *l);
Position ListFirst(const List *l);
Position ListLast(const List *l);
Position ListAdvance(const List *l, Position p);
Position ListPrevious(const List *l, Position p);
void *ListRetrieve(const List *l, Position p);
bool ListInsert(List *l, Position p, void *item);
void ListDelete(List *l, Position p);
typedef void ListCallback(const void *);
void ListTraverse(const List *l, ListCallback *fn, bool fwd);
#endif
Code:
// list.cpp - Linked List ADT
#include <stdlib.h>
#include "list.h"
struct List {
ListNode *head;
};
struct ListNode {
void *item;
ListNode *next;
};
static void reverse(Position p, ListCallback fn);
List *ListConstruct() {
List *l;
l = (List *)malloc(sizeof(List));
if (l == NULL) {
return NULL; // No memory
}
l->head = NULL;
return l;
}
void ListDestroy(List *l) {
while (!ListEmpty(l)) {
ListDelete(l, ListFirst(l));
}
free(l);
}
bool ListEmpty(const List *l) {
return l->head == NULL;
}
Position ListHead(const List *l) {
return NULL;
}
Position ListFirst(const List *l) {
return l->head;
}
Position ListLast(const List *l) {
Position p;
p = l->head;
if (p == NULL) {
return NULL;
}
while (p->next != NULL) {
p = p->next;
}
return p;
}
Position ListAdvance(const List *l, Position p) {
if (p == NULL) {
p = l->head;
}
else {
p = p->next;
}
return p;
}
Position ListPrevious(const List *l, Position p) {
ListNode *tmp;
if (p == NULL || l->head == p) {
return NULL;
}
tmp = l->head;
while (tmp != NULL && tmp->next != p) {
tmp = tmp->next;
}
return tmp;
}
void *ListRetrieve(const List *l, Position p) {
if (p == NULL ) {
return NULL;
}
return p->item;
}
bool ListInsert(List *l, Position p, void *item) {
ListNode *tmp;
tmp = (ListNode *)malloc(sizeof(ListNode));
if (tmp == NULL) {
return false; // No memory
}
tmp->item = item;
if (p == NULL) { // insert at head
tmp->next = l->head;
l->head = tmp;
}
else {
tmp->next = p->next;
p->next = tmp;
}
return true;
}
void ListDelete(List *l, Position p) {
ListNode *prev;
if (p == NULL) {
return; // For safety
}
prev = ListPrevious(l, p);
if (prev == NULL) { // must be head node
l->head = p->next;
}
else {
prev->next = p->next;
}
free(p);
}
void ListTraverse(const List *l, ListCallback fn, bool fwd) {
ListNode *p;
if (fwd) {
for (p = l->head; p != NULL; p = p->next) {
fn(p->item);
}
}
else {
reverse(l->head, fn);
}
}
static void reverse(Position p, ListCallback fn) {
if (p != NULL) {
reverse(p->next, fn);
fn(p->item);
}
}
Code:
#include <stdlib.h>
#include <stdio.h>
#include "list.h"
//the callback function
void printname(void *ptr) {
printf("%s\n", (char *)ptr);
}
int main() {
List *l;
position p;
if ((l = ListConstruct()) == NULL) {
exit(EXIT_FAILURE); //unable to create list
}
p = ListHead(l); // start at front of enpty list
//insert an item at the front
if (!ListInsert(l,p, "Freddy")) {
exit(EXIT_FAILURE);
}
//insert another item after that - move position first
p = ListNext(l,p);
if (!ListInsert(l, p, "Billy")) {
exit(EXIT_FAILURE);
}
//now insert a third one before the last
if (!ListInsert(l, p, "Johnny")) {
exit(EXIT_FAILURE);
}
//Finally the last one at the end
p=ListLast(l);
if (!ListInsert(l, p, "Mickey")) {
exit(EXIT_FAILURE);
}
// Now print out the list in the forward direction
ListTraverse(l, printname, true);
//destroy the list before finishing
ListDestroy(l);
return 0;
}
Thanks for your help
PT
