Learning Algorithms and Data Structures: Linked Lists
Lareen Melo ✨ ・3 min read
Learning Algorithms and Data Structures (4 Part Series)
A linked list is a linear collection of data items where each item has some form of link connection to other items. A more lowlevel explanation is that linked lists are chunks of memory that are bound together by pointers.
The Lingo (and some important technicalities)
 The items within a linked list are called nodes
 Linked lists are usually implemented with a head and tail node
 A tail represents the last node of a linked list
 The head of a linked list refers to the first node
Pros and cons
Pros ✅
 Linked lists can have constant time for operations like insertion/deletion at the head or tail
 Dynamic at runtime
Cons 👎
 Accessing elements by index requires transversing the list
 Extra space for pointers
Linked Lists vs. Arrays
 Arrays have better memory locality and cache performance. This is because linked lists have a random pointer jumping characteristic whereas arrays have contiguous traits.
 Linked lists do have better time complexities when performing insertion or deletions at head and tail depending on its implementation.
Types of Linked Lists
Singly Linked Lists
A singly linked list is a list where each node contains a reference to the next node.
Doubly Linked Lists
A doubly linked list is a list where each node contains a reference to the next node and the previous node.
Pros & cons
Pros ✅
 Easier to manipulate
Cons 👎
 It requires more space per node due to the two references (previous and next)
 Elementary operations like insertion and deletion are a bit more expensive
Circular Linked Lists
A circular linked list is a list where the last node’s next reference is the head of the list. Basically, recreating a loop. A circular linked can be implemented as a singly or doubly one.
Method complexities
The complexities of the methods of a linked list vary according to its implementation. If the list has a tail reference certain operations can become constant time, otherwise, they're linear.

Insertion:
 Beginning: O(1)
 End:
 if the last node is known O(1)
 if it’s not known O(N)
 Anywhere else: O(N)

Deletion
 Beginning: O(1)
 End:
 if the last node is known O(1)
 if it’s not known O(N)
 Anywhere else: O(N)
Transversion: O(N)
When transversing a circular linked list be careful with that loop! A good way to stop going into a loop is to have a flag type variable that raises when you’re visiting a node for the second time. Or just validating if you’re at the last node (which is supposed to have a ‘next’ pointer to the first node).
Implementation
During this step of the challenge, I implemented the 3 types of linked lists I mentioned in Swift and C++. For the sake of the article, I will only show my doubly circular linked list implementation in C++ (although I also implemented a singly circular linked list in Swift and C++).
I was tired of repeating the same methods all over again so for this implementation I just worked with the basic insertion and deletion. For more detailed implementations do check out my algorithms repo on GitHub!
Problemsolving
So a good thing about linked lists is the fact that they’re a data structure easy to visualize, especially if you draw them. It’s easy to solve problems by having the visual aid there. It took me more than a day of solving problems to come to this conclusion because I wasn’t used to working with pointers and I had to go through a lot of aha’s to be able to solve most of them right of the bat. But I kept on practicing and now I think I’m fine. I will keep using the visual aiding technique from now on!
ON TO THE NEXT ONE: Stacks.
^{ Follow my competitive programming journey on: https://github.com/lareenmelo/algorithms 💓 }
Learning Algorithms and Data Structures (4 Part Series)
In the
head == tail
branch ofremove()
, you set bothhead
andtail
tonullptr
withoutdelete
what they pointed to, leaking the last Node in the list.For more on manual memory management for linked list, check out Learning Rust with Entirely Too Many Linked Lists. Rust actually enforces many C++ core guidelines for guarding against pointer mistakes. For example, in your case you are in fact implementing adhoc reference counting pointers. Properly implementing reference counting pointer or using the standard one would have saved you from thinking about
new
anddelete
and prevented the leaking problem.For even more on linked list, Lisp (Scheme) is where the full depth is at. Maybe pick up The Little Schemer when you have time.
Thank you for the feedback!
I didn't notice the leak since I haven't really worked with pointers before. To be completely honest I found it hard to understand and work with them. I will definitely check out the resources you've mentioned so that I improve in this matter.
Again, thank you for the feedback and the resources!