Doubly Linked List - Pointers vs Arrays
Introduction
There has been quite a ruckus the past few days on DLL and in this post I want to add a different point of view: why you should be using Arrays instead of Pointers when writing DLL.
Note: The context of this post is for data with known sizes where using array is ideal. If the type of data you're working on has unknown sizes, you might have to use the pointers method.
What is DLL - Doubly Linked List?
There are plenty of resources on this, some of them:
Use cases of DLL:
- Browser history (back and forward navigation).
- Music player playlists.
- Undo/Redo functionality.
- Implementing complex data structures: LRU (Least Recently Used) caches.
- Text editor and IDE.
- OS scheduling.
The code in C
I'm going to provide the code using diff in Neovim..at first it will look noisy visually but after awhile you'll see it helps on understanding the difference between the two version: using Pointers vs using Arrays.
--Note--: on PC you need to "Open image in new tab" then double click the image for it to zoom-in. On mobile phone you can just pinch-zoom to enlarge the image.
Highlights
Pointers in the left split:
- createNode function to create new node and do manual memory allocation.
Arrays in the right split:
- initializeArray function: a simple for loop.
Nothing particularly interesting / worth noting in the second image. Don't forget to free the memory if you're using pointers!
Benchmark
We have arrived at my favorite part: lets run some benches!
The array version ran 4.39x faster than the pointers version
Conclusion
So there you go, writing DLL using Arrays is both faster and safer. Why safer? You need to read up on why working with raw pointers are dangerous and prone to memory errors.
Some pros of using Arrays:
- Simpler: no need for manual memory management.
- Faster access due contiguous memory (better cache locality).
Some cons of using Pointers:
- Complex: required to do manual memory management (allocation & dealloaction).
- Slower process, has to allocate memory each time.
- Prone to memory errors (dangling pointers).
I'm keeping this post short and concise as I want to point out or even spread the word to normalize the use of arrays instead of pointers in C programming when you can.
Addendum
[Update] : To make it more fair, I've added some points on the pros-cons consideration.
Main cons of using Arrays method:
- Not flexible, static memory size.
- Limited to data with known size ranges.
Main pros of using Pointers method:
- Flexibility of expanding the size of memory required.
- Works with any data size range.
So yeah, the pointers method provides flexibility (which can be important factor for some use cases)...however in my opinion we should put a limit on everything:
we should know exactly what our data looks like and its characteristics (its mutability, size, source, etc).
I'm inspired by Tigerbeetle and its Tiger-style programming, the folks over there know exactly their data in and out, they understand it so well they never need to manually allocate memory.
Everything is on stack, no need to free memory.
In the near future I might write articles covering some of the most important points in Tiger-style programming..they are very good!
Note: I compiled both programs using gcc -O3 optimization level. Also I've made a new Github Gist repo for the codes I post in my Bearblog, so going forward I'm not using Pastebin anymore and will utilize Github Gist instead. This is my 3rd Github account, why the multiple accounts you ask? This is my way of doing "separation of concerns" or "compartmentalization" : 1 for work stuff, 1 for hobby/side-projects, 1 for Bearblog codes.
Gist code repo: