DEV Community

loading...

Learning Algorithms and Data Structures: Linked Lists

lareenmelo profile image Lareen Melo ✨ ・3 min read

A linked list is a linear collection of data items where each item has some form of link connection to other items. A more low-level 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++).

Alt Text

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!

Problem-solving

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 💓

Discussion (2)

Collapse
louy2 profile image
Yufan Lou

In the head == tail branch of remove(), you set both head and tail to nullptr without delete 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 ad-hoc reference counting pointers. Properly implementing reference counting pointer or using the standard one would have saved you from thinking about new and delete 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.

Collapse
lareenmelo profile image
Lareen Melo ✨ Author

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!

Forem Open with the Forem app