Lists, Linked, and Otherwise

Abstract Data Types

An abstract data type (ADT) is a way to describe a data structure in terms of what operations it supports and the rules for using it, without worrying about how it’s implemented. This separation of concerns allows us to focus on the problem at hand without getting bogged down in the details of the implementation.

Lists

A list is a collection of elements that are ordered in a linear sequence. Some basic operations that lists support include:

• Insert: Add an element to the list at a specific position.
• Delete: Remove an element from the list at a specific position.
• Get: Retrieve an element from the list at a specific position.

Linked Lists

A linked list is a data structure that consists of a sequence of elements, where each element points to the next element in the sequence. This allows for efficient insertion and deletion operations, as elements can be easily rearranged by changing the pointers.

To traverse a linked list (or retrieve an element at a specific position), you start at the head pointer and follow the pointers to the desired element. This results in a time complexity of $O(N)$ for traversal, as you may need to visit every element in the list.

Compared to arrays, linked lists have the following advantages and disadvantages:

• Advantages:
  • Dynamic size: Linked lists can grow or shrink in size as needed.
  • Efficient insertion and deletion: Inserting or deleting an element in a linked list is $O(1)$, as you only need to update the pointers.
  • No wasted space: Linked lists only use as much memory as needed for the elements.
• Disadvantages:
  • No random access: To access an element at a specific position, you need to traverse the list from the beginning, resulting in $O(N)$ time complexity.

Tip

More efficient implementations of a linked list as a result, have a field for size to keep track of the number of elements in the list, in order to avoid traversing the list to find the size.

Singly Linked List

In a singly linked list, each element points to the next element in the sequence. The last element points to null to indicate the end of the list.

The head pointer points to the first element in the list.

graph LR
    head --> A
    A-- next --> B
    B -- next --> C
    C -- next --> D
    D -- next --> null

Tip

A tail pointer can be added to the list to keep track of the last element, allowing for efficient insertion at the end of the list. This is seen in the next example, Doubly Linked Lists.

Doubly Linked List

In a doubly linked list, each element points to both the next and previous elements in the sequence. This allows for efficient traversal in both directions.

The head pointer points to the first element in the list, and the tail pointer points to the last element.

graph LR
    head --> A
    A -- next --> B
    B -- prev --> A
    B -- next --> C
    C -- prev --> B
    C -- next --> D
    D -- prev --> C
    D -- next --> null
    tail --> D

Source

The existing course note was retained and normalized during the merge.

Related: Topic index.