October 03, 2019

Linked lists vs object oriented programming

A linked list is good example for comparing classical structured programming with modern object oriented one. For the programming language C, a linked list is the most advanced form of data storage. It is superior to an array of structs, because a linked list allocates memory dynamically. A linked list implementation in C works the same way, like a python dictionary. The programmer can create a hierarchical database and then store values into the storage. Nearly all advanced C programs are using for internal storage a linked list. Either with a self-implemented retrieval algorithm or with a standard library.

The interesting point is, that for object oriented languages like C++, Java and Python a linked list isn't very important. It is used seldom and in most cases it's equal to a bad design. The reason is, that the concept of a class and the ability to store a class in an array is more powerful than a linked list. Let me give an example:

Suppose a game written in C has to store obstacles on a map. Each obstacle contains of a position, a size and a color. The natural way for realizing such datastructure in C is a linked list. There is no need to define the amount of obstacles in advanced, but the list can grow on the fly. It's easy to store new items into the list and retrieve existing one. The combination of the C language plus a linked list, allows to create a fast video game.

A C++ programmer will realize the same feature with a vector of objects. He defines first a class for the obstacle and then adds an object to an empty vector. The same technique is used by Python programmers, and Java coders. The difference is, that in object oriented programming language the programmers are not machine oriented, but are describing a domain. How the compiler is converting the list of classes into a memory representation is not important for the programmer.

Now it's possible to compare linked lists with a vector of class-objects. The main difference is, that a linked list holds only the data but not the program code. In a c program there a 20 subroutines who have all access to the linked list. It's equal to a centralized data-class in C++. That means, the programmer defines a class for information storage but the routines for updating the class are outsourced in a different class. This simplifies the interchange of information between different parts of the program.

According to the OOP paradigm, information interchange has to be prevented. The idea behind creating different classes is, that they can't modify external information. So a linked list and object oriented design is the opposite. The reason, why OOP has become successful is because larger software projects can be implemented more easily. That means, a linked list work only for small amount of codelines. Only C++ like languages are supporting bigger software projects.