Java Linked List implementation equivalent in C?

**pbtrn10k** · 08-19-2009

Firstly I do know how linked lists work and am a begginer in C but mildly competent.

In the last few lectures of term in my CompSci course the lecturer gave us some examples of Java classes and their equivalent C representations - his main example was a Hashset implementation and I am trying to replicate his approach with a linked list. The idea is to have the methods for the list embedded in the struct, so to add a new element one would do list->addToHead(list,item).

I'm getting a lot of compile time errors with my code though, most of which I don't understand fully. My code is below

PS - Yeah I know this is a trivial excercise, and not the best way to write C code, I'm just playing with this approach to try to get it to work!

Code:

Code:

#include <stdlib.h>
#include "bool.h"

// Struct Definitions
//=========================

#define node_t struct _node_t
node_t {
  // node contents
  void *item;
  node next, prev;
  
  // utility methods
  void (*insertBetween) (node THIS, node prev, node next);
  void (*remove) (node THIS);
  
} *node;

#define linkedList_t struct _linkedList_t
linkedList_t {
  // list contents
  node head,tail;
  int size;
  
  // add to list methods
  void (*addToTail) (linkedList THIS, void *item);
  void (*addToHead) (linkedList THIS, void *item);
  void (*addAtIndex) (linkedList THIS, void *item, int index);
  
  // remove from list methods
  void (*removeByIndex) (linkedList THIS, int index);
  void (*removeByItem) (linkedList THIS, void *item);
  
  // utility methods
  int (*indexOf) (linkedList THIS, void *item);
  node (*nodeOf) (linkedList THIS, void *item)
  node (*nodeAtIndex) (linkedList THIS, int index);
  boolean (*contains) (linkedList THIS, void *item);
  boolean (*isEmpty) (linkedList THIS, void *item);
  
} *linkedList;

// Method Definitions
//=========================

// node constructor
node newNode(void *item);

// linked list constructor
linkedList newLinkedList();

// Method Implementations
//=========================

// INTERNAL NODE METHODS

  // insertion
  void insertBetween (node THIS, node prev, node next)
  {
    THIS->prev = prev;
    THIS->next = next;
    prev->next = THIS;
    next->prev = THIS;
  }
  void remove (node THIS)
  {
    THIS->prev->next = THIS->next;
    THIS->next->prev = THIS->prev;
    THIS->next = NULL;
    THIS->prev = NULL;
  }
  
// INTERNAL LINKED LIST METHODS

  // add methods
  void addToTail (linkedList THIS, void *item)
  {
    node add = newNode(item);
    add->insertBetween(add, THIS->tail->prev, THIS->tail);
    THIS->size = THIS->size + 1;
  }
  void addToHead (linkedList THIS, void *item)
  {
    node add = newNode(item);
    add->insertBetween(add, THIS->head, THIS->head->next);
    THIS->size = THIS->size + 1;
  }
  void addAtIndex (linkedList THIS, void *item, int index)
  {
    if (index == 0)
      addToHead(THIS,item);
    else
    {
      node cur = nodeAtIndex(index-1);
      node add = newNode(item);
      add->insertBetween(add,cur,cur->next);
    }
  }
  
  // remove methods
  void removeByIndex (linkedList THIS, int index)
  {
    node cur = nodeAtIndex(index);
    cur->remove(cur);
    free(cur);
  }
  void removeByItem (linkedList THIS, void *item)
  {
    node cur = nodeOf(item);
    cur->remove(cur);
    free(cur);
  }
  
  // utility methods
  int indexOf(linkedList THIS, void *item)
  {
    int i=0;
    node cur=THIS->head->next;
    while (i < index && cur->item != item)
    {
      cur = cur->next;
      i++;
    }
    if (cur->item == item)
      return i;
    return -1;
  }
  node nodeOf(linkedList THIS, void *item)
  {
    int i=0;
    node cur=THIS->head->next;
    while (i < index && cur->item != item)
    {
      cur = cur->next;
      i++;
    }
    if (cur->item == item)
      return cur;
    return NULL;
  }
  node nodeAtIndex(linkedList THIS, int index)
  {
    if (index >= size)
      return NULL;
    int i=0;
    node cur=THIS->head->next;
    while (i < index)
    {
      cur = cur->next;
      i++;
    }
    return cur;
  }
  boolean contains(linkedList THIS, void *item)
  {
    return ( indexOf(THIS, item) != -1 );
  }
  boolean isEmpty(linkedList THIS)
  {
    return (head->next == tail);
  }

// CONSTRUCTORS

  // node constructor
  node newNode(void *item)
  {
    // memory allocation
    node THIS = (node) (malloc( sizeof(node_t) ));
    
    // fields
    THIS->next = THIS;
    THIS->prev = THIS;
    THIS->item = THIS;
    
    // methods
    THIS->insertBetween = insertBetween;
    THIS->remove = remove;
    
    //return
    return THIS;
    
  }
  
  // list constructor
  linkedList newLinkedList()
  {
    // memory allocation
    linkedList THIS = (linkedList) (malloc( sizeof(linkedList_t) ));
    
    // fields
    THIS->head = newNode(NULL);
    THIS->tail = newNode(NULL);
      head->next = THIS->tail;
      tail->prev = THIS->head;
      
    // methods
      // add methods
      THIS->addToTail = addToTail;
      THIS->addToHead = addToHead;
      THIS->addAtIndex = addAtIndex;
      
      // remove methods
      THIS->removeByIndex = removeByIndex;
      THIS->removeByItem = removeByItem;
      
      // utility methods
      THIS->indexOf = indexOf;
      THIS->nodeOf = nodeOf;
      THIS->nodeAtIndex = nodeAtIndex;
      THIS->contains = contains;
      THIS->isEmpty = isEmpty;
      
    //return
    return THIS;
  }

Errors:

Code:

lib/linkedlist.h:10: error: expected specifier-qualifier-list before ‘node’                                
lib/linkedlist.h:21: error: expected specifier-qualifier-list before ‘node’
lib/linkedlist.h:46: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘newNode’
lib/linkedlist.h:49: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘newLinkedList’
lib/linkedlist.h:57: error: expected ‘)’ before ‘THIS’
lib/linkedlist.h:64: error: expected ‘)’ before ‘THIS’
lib/linkedlist.h:75: error: expected ‘)’ before ‘THIS’
lib/linkedlist.h:81: error: expected ‘)’ before ‘THIS’
lib/linkedlist.h:87: error: expected ‘)’ before ‘THIS’
lib/linkedlist.h:100: error: expected ‘)’ before ‘THIS’
lib/linkedlist.h:106: error: expected ‘)’ before ‘THIS’
lib/linkedlist.h:114: error: expected ‘)’ before ‘THIS’
lib/linkedlist.h:127: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘nodeOf’
lib/linkedlist.h:140: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘nodeAtIndex’
lib/linkedlist.h:153: error: expected ‘)’ before ‘THIS’
lib/linkedlist.h:157: error: expected ‘)’ before ‘THIS’
lib/linkedlist.h:165: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘newNode’
lib/linkedlist.h:185: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘newLinkedList’

Any help is greatly appreciated!

**KBriggs** · 08-19-2009

All except the first two errors are just missing semicolons and closing brackets, just go through and clean up your code and they will go away.

Also, open question: can C structs contain function declarations? I thought that was OO only.

**pbtrn10k** · 08-19-2009

Yes the first two errors are confusing, but ifyou look closely all the other errors after that aren't quite as simple as they appear to be. For example this error

Code:

lib/linkedlist.h:46: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘newNode’

relates to this line:

Code:

node newNode(void *item);

I have a feeling that if the first two errors were resolved, and the types node and linkedList were properly created (as I don't think they are being) all these other problems would go away too.

In the examples we were given the structs did contain method definitions. I looked into this a bit and it is possible, the same way it is possible to pass functions by pointer. The structs simply contain pointers to functions.

I should have mentioned - I gather that the first two errors occur normally if a name hasn't been specified before the struct is defined. E.g.

Code:

typedef struct { /*contents*/ } *node;

instead of

Code:

typedef struct node_t { /*contents*/ } *node;

But this is just from googling around, so I may be wrong.

**laserlight** · 08-19-2009

Originally Posted by pbtrn10k

I'm getting a lot of compile time errors with my code though, most of which I don't understand fully. My code is below

Looking at your code, I get the impression that you want the identifier node to be a pointer to a node structure, which you name node_t. I suggest that you keep the pointer notation, and instead define:

Code:

typedef struct node node;

struct node {
    /* node contents */
    void *item;
    node *next;
    node *prev;

    /* utility methods */
    void (*insertBetween)(node *this, node *prev, node *next);
    void (*remove)(node *this);
};

node *newNode(void *item);

Notice that I changed the #define to a typedef, and that I no longer created a global pointer to a node structure (which was what you were doing previously).

Originally Posted by KBriggs

Also, open question: can C structs contain function declarations? I thought that was OO only.

Those are function pointer declarations. That said, pbtrn10k might be intending to simulate OO later, otherwise it seems to me that those declarations would not be useful.

**pbtrn10k** · 08-19-2009

I carried out the changes you suggested and although they do remove the first two errors I still get the other errors about missing ;, ) etc. They are still said to be missing in the middle of lines of code though.

Here's the new code:

Code:

#include <stdlib.h>
#include "bool.h"

// Struct Definitions
//=========================

typedef struct node node
{
  // node *contents
  void *item;
  node *next, *prev;
  
  // utility methods
  void (*insertBetween) (node *THIS, node *prev, node *next);
  void (*remove) (node *THIS);
  
};

typedef struct linkedList linkedList
{
  // list contents
  node *head, *tail;
  int size;
  
  // add to list methods
  void (*addToTail) (linkedList *THIS, void *item);
  void (*addToHead) (linkedList *THIS, void *item);
  void (*addAtIndex) (linkedList *THIS, void *item, int index);
  
  // remove from list methods
  void (*removeByIndex) (linkedList *THIS, int index);
  void (*removeByItem) (linkedList *THIS, void *item);
  
  // utility methods
  int (*indexOf) (linkedList *THIS, void *item);
  node* (*nodeOf) (linkedList *THIS, void *item)
  node* (*nodeAtIndex) (linkedList *THIS, int index);
  boolean (*contains) (linkedList *THIS, void *item);
  boolean (*isEmpty) (linkedList *THIS, void *item);
  
};

// Method Definitions
//=========================

// node *constructor
node* newNode(void *item);

// linked list constructor
linkedList* newLinkedList();

// Method Implementations
//=========================

// INTERNAL NODE METHODS

  // insertion
  void insertBetween (node *THIS, node *prev, node *next)
  {
    THIS->prev = prev;
    THIS->next = next;
    prev->next = THIS;
    next->prev = THIS;
  }
  void remove (node *THIS)
  {
    THIS->prev->next = THIS->next;
    THIS->next->prev = THIS->prev;
    THIS->next = NULL;
    THIS->prev = NULL;
  }
  
// INTERNAL LINKED LIST METHODS

  // add methods
  void addToTail (linkedList *THIS, void *item)
  {
    node *add = newNode(item);
    add->insertBetween(add, THIS->tail->prev, THIS->tail);
    THIS->size = THIS->size + 1;
  }
  void addToHead (linkedList *THIS, void *item)
  {
    node *add = newNode(item);
    add->insertBetween(add, THIS->head, THIS->head->next);
    THIS->size = THIS->size + 1;
  }
  void addAtIndex (linkedList *THIS, void *item, int index)
  {
    if (index == 0)
      addToHead(THIS,item);
    else
    {
      node *cur = nodeAtIndex(index-1);
      node *add = newNode(item);
      add->insertBetween(add,cur,cur->next);
    }
  }
  
  // remove methods
  void removeByIndex (linkedList *THIS, int index)
  {
    node *cur = nodeAtIndex(index);
    cur->remove(cur);
    free(cur);
  }
  void removeByItem (linkedList *THIS, void *item)
  {
    node *cur = nodeOf(item);
    cur->remove(cur);
    free(cur);
  }
  
  // utility methods
  int indexOf(linkedList *THIS, void *item)
  {
    int i=0;
    node *cur=THIS->head->next;
    while (i < index && cur->item != item)
    {
      cur = cur->next;
      i++;
    }
    if (cur->item == item)
      return i;
    return -1;
  }
  node* nodeOf(linkedList *THIS, void *item)
  {
    int i=0;
    node *cur=THIS->head->next;
    while (i < index && cur->item != item)
    {
      cur = cur->next;
      i++;
    }
    if (cur->item == item)
      return cur;
    return NULL;
  }
  node* nodeAtIndex(linkedList *THIS, int index)
  {
    if (index >= size)
      return NULL;
    int i=0;
    node *cur=THIS->head->next;
    while (i < index)
    {
      cur = cur->next;
      i++;
    }
    return cur;
  }
  boolean contains(linkedList *THIS, void *item)
  {
    return ( indexOf(THIS, item) != -1 );
  }
  boolean isEmpty(linkedList THIS)
  {
    return (head->next == tail);
  }

// CONSTRUCTORS

  // node *constructor
  node* newNode(void *item)
  {
    // memory allocation
    node *THIS = (node) (malloc( sizeof(node_t) ));
    
    // fields
    THIS->next = THIS;
    THIS->prev = THIS;
    THIS->item = THIS;
    
    // methods
    THIS->insertBetween = insertBetween;
    THIS->remove = remove;
    
    //return
    return THIS;
    
  }
  
  // list constructor
  linkedList* newLinkedList()
  {
    // memory allocation
    linkedList *THIS = (linkedList) (malloc( sizeof(linkedList_t) ));
    
    // fields
    THIS->head = newNode(NULL);
    THIS->tail = newNode(NULL);
      head->next = THIS->tail;
      tail->prev = THIS->head;
      
    // methods
      // add methods
      THIS->addToTail = addToTail;
      THIS->addToHead = addToHead;
      THIS->addAtIndex = addAtIndex;
      
      // remove methods
      THIS->removeByIndex = removeByIndex;
      THIS->removeByItem = removeByItem;
      
      // utility methods
      THIS->indexOf = indexOf;
      THIS->nodeOf = nodeOf;
      THIS->nodeAtIndex = nodeAtIndex;
      THIS->contains = contains;
      THIS->isEmpty = isEmpty;
      
    //return
    return THIS;
  }

And here's the new errors:

Code:

lib/linkedlist.h:8: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘{’ token               
lib/linkedlist.h:20: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘{’ token              
lib/linkedlist.h:47: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘*’ token
lib/linkedlist.h:50: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘*’ token
lib/linkedlist.h:58: error: expected ‘)’ before ‘*’ token
lib/linkedlist.h:65: error: expected ‘)’ before ‘*’ token
lib/linkedlist.h:76: error: expected ‘)’ before ‘*’ token
lib/linkedlist.h:82: error: expected ‘)’ before ‘*’ token
lib/linkedlist.h:88: error: expected ‘)’ before ‘*’ token
lib/linkedlist.h:101: error: expected ‘)’ before ‘*’ token
lib/linkedlist.h:107: error: expected ‘)’ before ‘*’ token
lib/linkedlist.h:115: error: expected ‘)’ before ‘*’ token
lib/linkedlist.h:128: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘*’ token
lib/linkedlist.h:141: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘*’ token
lib/linkedlist.h:154: error: expected ‘)’ before ‘*’ token
lib/linkedlist.h:158: error: expected ‘)’ before ‘THIS’
lib/linkedlist.h:166: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘*’ token
lib/linkedlist.h:186: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘*’ token

Originally Posted by laserlight

Those are function pointer declarations. That said, pbtrn10k might be intending to simulate OO later, otherwise it seems to me that those declarations would not be useful.

The object of the lectures in question was to show how OO can be simulated in a non-OO language like C. That said, I'm doing this to learn and because our lecturer has a reputation for putting code in his handouts which doesn't compile, so I want to see if he was actually telling the truth!!

**laserlight** · 08-19-2009

Originally Posted by pbtrn10k

I carried out the changes you suggested and although they do remove the first two errors I still get the other errors about missing ;, ) etc. They are still said to be missing in the middle of lines of code though.

Notice that in my example the typedef comes before and is separate from the struct definition.

**pbtrn10k** · 08-19-2009

Fantastic! There were also some other problems in the code which I got ironed out. Here's the final version:

Code:

#include <stdlib.h>
#include "bool.h"

// Struct Definitions
//=========================

typedef struct node node;

struct node {
  // node *contents
  void *item;
  node *next, *prev;
  
  // utility methods
  void (*insertBetween) (node *THIS, node *prev, node *next);
  void (*removeFromList) (node *THIS);
  
};

typedef struct linkedList linkedList;

struct linkedList {
  // list contents
  node *head, *tail;
  int size;
  
  // add to list methods
  void (*addToTail) (linkedList *THIS, void *item);
  void (*addToHead) (linkedList *THIS, void *item);
  void (*addAtIndex) (linkedList *THIS, void *item, int index);
  
  // remove from list methods
  void (*removeByIndex) (linkedList *THIS, int index);
  void (*removeByItem) (linkedList *THIS, void *item);
  
  // utility methods
  int (*indexOf) (linkedList *THIS, void *item);
  node* (*nodeOf) (linkedList *THIS, void *item);
  node* (*nodeAtIndex) (linkedList *THIS, int index);
  boolean (*contains) (linkedList *THIS, void *item);
  boolean (*isEmpty) (linkedList *THIS);
  
};

// Method Definitions
//=========================

// node *constructor
node* newNode(void *item);

// linked list constructor
linkedList* newLinkedList();

// node methods
void insertBetween(node *THIS, node *prev, node *next);
void removeFromList(node *THIS);
  
// list methods
void addToTail(linkedList *THIS, void *item);
void addToHead(linkedList *THIS, void *item);
void addAtIndex(linkedList *THIS, void *item, int index);
void removeFromListByIndex(linkedList *THIS, int index);
void removeFromListByItem(linkedList *THIS, void *item);
int indexOf(linkedList *THIS, void *item);
node* nodeOf(linkedList *THIS, void *item);
node* nodeAtIndex(linkedList *THIS, int index);
boolean contains(linkedList *THIS, void *item);
boolean isEmpty(linkedList *THIS);

// Method Implementations
//=========================

// INTERNAL NODE METHODS

  // insertion
  void insertBetween (node *THIS, node *prev, node *next)
  {
    THIS->prev = prev;
    THIS->next = next;
    prev->next = THIS;
    next->prev = THIS;
  }
  void removeFromList (node *THIS)
  {
    THIS->prev->next = THIS->next;
    THIS->next->prev = THIS->prev;
    THIS->next = NULL;
    THIS->prev = NULL;
  }
  
// INTERNAL LINKED LIST METHODS

  // add methods
  void addToTail (linkedList *THIS, void *item)
  {
    node *add = newNode(item);
    add->insertBetween(add, THIS->tail->prev, THIS->tail);
    THIS->size = THIS->size + 1;
  }
  void addToHead (linkedList *THIS, void *item)
  {
    node *add = newNode(item);
    add->insertBetween(add, THIS->head, THIS->head->next);
    THIS->size = THIS->size + 1;
  }
  void addAtIndex (linkedList *THIS, void *item, int index)
  {
    if (index == 0)
      addToHead(THIS,item);
    else
    {
      node *cur = nodeAtIndex(THIS, index-1);
      node *add = newNode(item);
      add->insertBetween(add,cur,cur->next);
    }
  }
  
  // removeFromList methods
  void removeByIndex (linkedList *THIS, int index)
  {
    node *cur = nodeAtIndex(THIS, index);
    cur->removeFromList(cur);
    free(cur);
  }
  void removeByItem (linkedList *THIS, void *item)
  {
    node *cur = nodeOf(THIS, item);
    cur->removeFromList(cur);
    free(cur);
  }
  
  // utility methods
  int indexOf(linkedList *THIS, void *item)
  {
    int i=0;
    node *cur=THIS->head->next;
    while (i < THIS->size && cur->item != item)
    {
      cur = cur->next;
      i++;
    }
    if (cur->item == item)
      return i;
    return -1;
  }
  node* nodeOf(linkedList *THIS, void *item)
  {
    int i=0;
    node *cur=THIS->head->next;
    while (i < THIS->size && cur->item != item)
    {
      cur = cur->next;
      i++;
    }
    if (cur->item == item)
      return cur;
    return NULL;
  }
  node* nodeAtIndex(linkedList *THIS, int index)
  {
    if (index >= THIS->size)
      return NULL;
    int i=0;
    node *cur=THIS->head->next;
    while (i < index)
    {
      cur = cur->next;
      i++;
    }
    return cur;
  }
  boolean contains(linkedList *THIS, void *item)
  {
    return ( indexOf(THIS, item) != -1 );
  }
  boolean isEmpty(linkedList *THIS)
  {
    return (THIS->head->next == THIS->tail);
  }

// CONSTRUCTORS

  // node *constructor
  node* newNode(void *item)
  {
    // memory allocation
    node *THIS = (node *) (malloc( sizeof(node) ));
    
    // fields
    THIS->next = THIS;
    THIS->prev = THIS;
    THIS->item = THIS;
    
    // methods
    THIS->insertBetween = insertBetween;
    THIS->removeFromList = removeFromList;
    
    //return
    return THIS;
    
  }
  
  // list constructor
  linkedList* newLinkedList()
  {
    // memory allocation
    linkedList *THIS = (linkedList *) (malloc( sizeof(linkedList) ));
    
    // fields
    THIS->head = newNode(NULL);
    THIS->tail = newNode(NULL);
      THIS->head->next = THIS->tail;
      THIS->tail->prev = THIS->head;
      
    // methods
      // add methods
      THIS->addToTail = addToTail;
      THIS->addToHead = addToHead;
      THIS->addAtIndex = addAtIndex;
      
      // remove methods
      THIS->removeByIndex = removeByIndex;
      THIS->removeByItem = removeByItem;
      
      // utility methods
      THIS->indexOf = indexOf;
      THIS->nodeOf = nodeOf;
      THIS->nodeAtIndex = nodeAtIndex;
      THIS->contains = contains;
      THIS->isEmpty = isEmpty;
      
    //return
    return THIS;
  }

I only have one question left - why does your suggestion work?!

**tabstop** · 08-19-2009

What -- putting the typedef elsewhere? Typedef creates a name -- but it doesn't create the name until the statement is finished. So

Code:

typedef struct node {
    int bob; //typedef not yet done
    struct node *next; //have to use the "real" name since the typedef not yet done
} node; //NOW we can use node

**laserlight** · 08-19-2009

Originally Posted by pbtrn10k

I only have one question left - why does your suggestion work?!

Your first try did not work because you were declaring node as a pointer to a struct _node_t. Your next try did not work because of a syntax error: you were placing the typedef name before the struct definition was complete. My suggestion works because it first declares node as an alias for struct node, and then defines struct node. Since node has been declared, you can use the name node within the definition of struct node. If not, you would have to go with tabstop's suggestion.

Thread: Java Linked List implementation equivalent in C?

Thread Tools

Search Thread

Display

Java Linked List implementation equivalent in C?

Similar Threads

C++ Linked list program need help !!!

Pleas take a look & give a critique

Anyone good with linked list.....I am not....

How can I traverse a huffman tree

singly linked list