01. Introduction to LinkedLists

What is a Linked List?

A linked list is a data structure that consists of a group of nodes that together represent a sequence.

Each node is composed of a generic data element and a reference to the next node in the sequence.

Comparison to Arrays

  • Arrays can be traversed randomly, while linked lists must be traversed sequentially.
  • Linked list can grow dynamically, while arrays must define a size before its instantiation.
  • Because arrays have fixed sizes, we must know the upper limit of the number of elements in advance.
  • Memory allocation for an array is compile time and linked list is run time.
  • Inserting elements into an array is expensive since we have to shift all elements coming after the insertion node over one. For linked lists, however, you can simply insert a node by reconfiguring the node coming before it.
  • Linked lists allow for dynamic resizing, making it easy to add more data.

Types of Linked Lists

There are several types of linked lists, but we'll begin by looking at the simplest - the singly-linked list.

A singly-linked list has only a NEXT pointer, which points to the next node in sequence. A doubly-linked list would have an additional PREV pointer that points to the previous node.

There is also a circular linked list, in which one next NEXT pointer points to a previous element.

A linked list made up of nodes.

The linking of a group of NODE objects is what gives us a linked list. Each NEXT pointer connects one node to the next. If the node is at the end, its NEXT pointer will point to NULL.

Head and Tail

Additionally, there are two more pointers in a linked list. The HEAD of the linked list holds the first node in the list, while the TAIL holds the last.

Performance

OperationAverageWorst
Space O(n) O(n)
Lookup O(n) O(n)
Insert O(n) O(n)
Delete O(n) O(n)

Ace your Technical Interview

Introduction to Algorithms

Ace your Technical Interview Try Algorithms

Introduction to Algorithms uniquely combines rigor and comprehensiveness. The book covers a broad range of algorithms in depth, yet makes their design and analysis accessible to all levels of readers. The algorithms are described in English and in a pseudocode designed to be readable by anyone who has done a little programming.

$ Check price
9999Amazon 4.5 logo(418+ reviews)

More Algorithms resources

Aching back from coding all day?

Self-Massage Tool

Aching back from coding all day? Try Back Problems

Relieve spasms, tight muscles, trigger points and pressure points with the Body Back Buddy! This trigger point massage is designed to help you self-message any area of your body - especially those that are hard to reach. Keeping your muscles relaxes and out of contraction is importan in helping to reduce pain and prevent muscle injury.

$ Check price
29.9529.95Amazon 4.5 logo(3,443+ reviews)

More Back Problems resources

Ad