3.8.1 Linked List

Knowledge Base > Algorithm > Data Structure

Overview

Linked List is a sequence of items arranged one after another, with each item connected to the next item by a ”link”. Hence, we can go through the collection sequentially. Each item contains the data and information of how to get to the next item. This keeps going until we meet the null link that points to no node, or we refer back to the first node, making the list a circular list. Normally, a linked list is referred as sequentially self-referenced data structure. The primary advantage behind this design over random access array is that linked list provides more capability to rearrange items much more efficiently. However, the trade off is expensive cost of quick access to any arbitrary items in the list, since the only way to get to an item is to follow links, one node after another one.

Basic Operation

• void insert(val):
  To insert a new node with given value at the head, middle, or tail of the list.
• void remove(val):
  To remove an existing node with given value at the head, middle, or tail of the list.

Source Code

There are two ways to implement a linked list. The first one is the simple one-way Linked List, whose elements are only linked to next node, or null if a tail node meets. The other implementation is similar, but lets elements link to next node or back to previous node. This two-way implementation is sometimes called Double Linked List.

• LinkedList (C)
  
  
• DoubleLinkedList (C)

Related Topics

• Stack
• Queue
• Tree