This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License
![]()
In this lesson, you will learn how to implement a “generic” linked list structure that can store any type of object. You should be able to adapt this technique to other data structures such as graphs or trees.
Each step of the lesson asks you to answer a question or write some code. Do the steps yourself before checking your work by revealing the answer.
You should also understand that both the LinkedList class and its Node inner class are generic. That means that this data structure can hold elements of any type, although with Java’s version of generics you still have to tell it what type that is when you create an instance of the class. You should understand how this is better than simply storing objects of type Object in your data structures (“type safety”, casting, etc.).
struct Employee “class” that we created in the Objects lesson and refined in the Reusable Code lesson.
For starters, copy the files Employee.h and Employee.c into your current project or working directory. We can now use the type Employee and the functions defined in the header file.
Node representing list nodes containing Employees and a “constructor” for such nodes.
#include <stdlib.h> to use malloc, but you knew that already.
LinkedList for a linked list of Nodes and a constructor for such linked lists.
Employee to a given LinkedList.
Employee in a given LinkedList, or NULL if the list is empty.
main function to test your LinkedList of Employees.
Download full program: list1.c
Employees. What if we wanted to hold other types of “objects” (pointers to structs)?Node structure, specifically the data member:
Employee data;
Each Node holds a pointer to an instance of a struct Employee, otherwise known as an Employee.
void* is defined to mean “pointer to an object of some type but I don't know what that type is.” This is sometimes called a “void pointer” (not to be confused with a null pointer). To allow the list to hold objects of any type, change the data member so that it holds a void* and adjust your “constructor” for Nodes.
LinkedList type or its constructor need to be changed?
Employees.
LinkedLists?
void* rather than Employee throughout:
void LinkedList_prepend(LinkedList this, void* data) {
Node node = new_Node(data);
if (node == NULL) {
// Out of memory!
}
node->next = this->head;
this->head = node;
}
void* LinkedList_first(LinkedList this) {
if (this->head == NULL) {
return NULL;
} else {
return this->head->data;
}
}
main function?
*** is the only line that’s different from the original.
Our LinkedLists now contain data elements of type void*. Any other pointer type is compatible with a void*, so we can pass e1 and e2 to LinkedList_prepend.
However LinkedList_first now returns a value of type void* also. If we want to treat it as the Employee that we know it is, we have to tell the C compiler that using a cast. We will come back to this at the end of this lesson.
Download full program: list2.c
LinkedList.h:
typedef struct LinkedList* LinkedList;
extern LinkedList new_LinkedList();
extern void LinkedList_prepend(LinkedList this, void *data);
extern void* LinkedList_first(LinkedList this);
Implementation LinkedList.c contains the type and function definitions (other than main). You will need to #include "LinkedList.h" in this file.
Put your main function in a separate file, e.g., list3.c:
#include <stdlib.h>
#include <stdio.h>
#include "Employee.h"
#include "LinkedList.h"
int main(int argc, char* argv[]) {
Employee e1 = new_Employee("Isaac Newton", 123);
Employee e2 = new_Employee("Albert Einstein", 456);
LinkedList list = new_LinkedList();
LinkedList_prepend(list, e1);
LinkedList_prepend(list, e2);
Employee e = (Employee)LinkedList_first(list); // ***
char* name = Employee_get_name(e);
printf("%s\n", name); // Albert Einstein
}
Compile all three files and link them together, for example: gcc -o list3 -std=c99 -Wall -Werror Employee.c LinkedList.c list3.c Then run the program to see its output.
Download files: LinkedList.h,
LinkedList.c,
list3.c
Employees rather than void pointers? Can you do it without rewriting all the code for the list? Try it!
EmployeeList with the same interface as the “generic” LinkedList, only using Employees instead of void*s. Here’s EmployeeList.h
#include "Employee.h"
#include "LinkedList.h"
typedef LinkedList EmployeeList;
extern EmployeeList new_EmployeeList();
extern void EmployeeList_prepend(EmployeeList this, Employee e);
extern Employee EmployeeList_first(EmployeeList this);
The typedef says that an EmployeeList “is a” LinkedList. It makes the two names refer to the same type. Unfortunately, this leaks the information about how an EmployeeList is implemented, breaking encapsulation. There are ways to avoid that (by defining another structure), but I’ll leave it for you to think about.
Here’s the implementation EmployeeList.c:
#include "EmployeeList.h"
EmployeeList new_EmployeeList() {
return new_LinkedList();
}
void EmployeeList_prepend(EmployeeList this, Employee e) {
LinkedList_prepend(this, e);
}
Employee EmployeeList_first(EmployeeList this) {
return (Employee)LinkedList_first(this);
}
And now you can use an EmployeeList and access its elements without the need for a cast:
#include <stdio.h>
#include "EmployeeList.h"
int main(int argc, char* argv[]) {
Employee e1 = new_Employee("Isaac Newton", 123);
Employee e2 = new_Employee("Albert Einstein", 456);
EmployeeList list = new_EmployeeList();
EmployeeList_prepend(list, e1);
EmployeeList_prepend(list, e2);
Employee e = EmployeeList_first(list); // no cast!
char* name = Employee_get_name(e);
printf("%s\n", name); // Albert Einstein
}
Note that our “wrapper class” will also prevent you from putting non-Employees into an EmployeeList. Try the following:
EmployeeList_prepend(list, "foobar");
You could still do it with LinkedList_prepend however, thanks to the typedef, and you’ll get strange behavior or a run-time error. Try it! That’s another reason not to do it this way. But I digress.