Data Structure & Algorithm Takeaway: Linear List

TipWhat is linear list?

Linear list is a collection of elements arranged in a linear order: $a_1,a_2,\dots ,a_n$. Each element in the list has a unique predecessor and successor, except for the first and last elements.

TipHow to store a linear list in computer memory?

A linear list can be represented in computer memory using two main methods:

1. Sequential storage: The elements of the linear list are stored in contiguous memory locations. This kind of linear list is called array.
2. Linked storage: Each element (node) contains a reference (pointer) to the next element in the list. This kind of linear list is called linked list.

TipWhat are the main operations of a linear list?

The basic operations of a linear list include:

• Structural operations:
  • Initialise a linear list with initial values;
  • Destroy a linear list;
  • Clear a linear list;
  • Check if the linear list is empty;
  • Get the length of the linear list.
• Element access operations:
  • Get an element by its index;
  • Search for an element by its value;
  • Traverse all elements with a specific operation on each element (such as printing).
• Element modification operations:
  • Update the value of an element by its index;
  • Insert a new element at a specific index;
    • Append an element to the end of the list;
    • Prepend an element to the beginning of the list;
  • Delete an element from a specific index;
    • Delete the last element of the list;
    • Delete the first element of the list.

The advanced operations include:

• Sorting the elements (which requires the elements to be comparable);

Some operations may not be applicable to all types of linear lists. For example, sorting requires the elements to be comparable.

Some special types of linear lists, such as stack and queue, may not support all operations due to their specific characteristics and constraints. These special types of linear lists are referred to as restricted linear lists.

TipWhy discussing the restricted linear lists like stack and queue separately, since they are also linear lists?

Some applications specifically require the operations that the restricted linear lists restrict themselves to, such as LIFO (Last In First Out) for stack and FIFO (First In First Out) for queue, even though they can be completed implemented as general linear lists by using the restricted operations only.