C for Java Programmers: Linked List

George Ferguson

Summer 2018
(Updated Summer 2020)

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License
Creative Commons 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.

How would (did) you implement a generic linked list data structure in Java?
The basic idea is to introduce a “list node” class that encapsulates the data elements and connects them into the linked list. Something like the following: class LinkedList<E> { class Node<E> { E data; Node<E> next; Node(E data) { this.data = data; this.next = null; } } Node<E> head; public void prepend(E element) { Node<E> node = new Node<E>(element); node.next = this.head; this.head = node; } } Of course you might have both head and tail pointers, you might use a doubly-linked list list, etc. You should understand what these things are and how and why they are used. But I digress.

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.).

C does not have generics, but we can use a couple of techniques to do something similar. Let's start by creating a linked list of employees, using the 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.

In a new C file, define the structured type Node representing list nodes containing Employees and a “constructor” for such nodes.
typedef struct Node* Node; struct Node { Employee data; struct Node* next; }; Node new_Node(Employee employee) { Node this = (Node)malloc(sizeof(struct Node)); if (this == NULL) { return NULL; // Out of memory } this->data = employee; this->next = NULL; return this; } You will need to #include <stdlib.h> to use malloc, but you knew that already.
In the same file, define the structured type LinkedList for a linked list of Nodes and a constructor for such linked lists.
typedef struct LinkedList* LinkedList; struct LinkedList { Node head; }; LinkedList new_LinkedList() { LinkedList this = (LinkedList)malloc(sizeof(struct LinkedList)); if (this == NULL) { return NULL; // Out of memory } this->head = NULL; return this; }
Define a function to prepend (add at the front) a given Employee to a given LinkedList.
void LinkedList_prepend(LinkedList this, Employee employee) { Node node = new_Node(employee); if (node == NULL) { // Out of memory! } node->next = this->head; this->head = node; }
Define a function to return the first Employee in a given LinkedList, or NULL if the list is empty.
Employee LinkedList_first(LinkedList this) { if (this->head == NULL) { return NULL; } else { return this->head->data; } }
Add a main function to test your LinkedList of Employees.
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 = LinkedList_first(list); char* name = Employee_get_name(e); printf("%s\n", name); // Albert Einstein }

Download full program: list1.c

Congratulations! It works. But there are a couple of issues with this code. Think about how you might address each of these, then continue the lesson.
On the question of what type of elements can be in the list, where is the type of the elements stored in the list defined?
In the 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.
In C, the type 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.
struct Node { void* data; struct Node* next; }; Node new_Node(void* data) { Node this = (Node)malloc(sizeof(struct Node)); if (this == NULL) { return NULL; // Out of memory } this->data = data; this->next = NULL; return this; }
Do the definition of your LinkedList type or its constructor need to be changed?
No they don’t. They don’t say anything about Employees.
What about the functions that apply to LinkedLists?
Yes they do, but it’s trivial to use 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; } }
What about your main function?
Yes. Can you spot the change(s)? 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 } The line marked *** 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

Now make this code reusable using the process described in the Reusable Code lesson.
Header file 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

One last thing: If you read the C for Java Programmers document, you know that casts are a common source of run-time errors. Our “generic” data structure requires any code that uses it to use casts everytime an element is retrieved from the list. Can you define a version of a linked list whose interface functions use Employees rather than void pointers? Can you do it without rewriting all the code for the list? Try it!
My approach would be to define an 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.

Back to Tutorial Home