Dynamic vs Static Data Structures: Linear Lists Explained

Posted on Feb 24, 2025 in Computers

Dynamic vs. Static Data Structures

Dynamic Structures:

Dynamic data structures are structures that grow as a program runs. A dynamic data structure is a collection of items called nodes, normally records. Unlike an array, which contains space for storing a number of elements, dynamic structures are used for the storage of real-world data that are constantly changing. A typical example of a static data structure is the list of passengers on an airline. If this list is kept in alphabetical order in an array, it would be necessary to make room to insert a new passenger in alphabetical order. This requires using a loop to copy the data record of each passenger into the next array element.

Static Structures:

A static data structure is one whose structure is specified at the time of writing the program and cannot be changed by the program. The values of its elements may vary, but not its structure, since it is fixed. A dynamic data structure can change its structure through the program. You can expand or limit its size while running the program.

Linear Lists

A linear list is a set of elements of a given type that can vary in number and in which each element has a unique predecessor and successor (or next one), except for the first and last on the list. This is a very broad definition that includes files and vectors. The linear list items are normally stored adjacent to one element after another in consecutive locations of memory. A linear list is stored in a computer’s main memory in successive positions of memory. When stored on magnetic tape, the successive elements are presented in succession on the tape.

Operations on Contiguous Linear Lists:

Insert, Delete, or locate an item.
Determine the size (number of elements) in the list.
Scroll down the list to locate a specific item.
Sort the items in the list in ascending or descending order.
Join two or more lists into a single list.
Divide a list into sublists or copy the delete list.

A linear list is stored in contiguous computer memory in successive adjacent positions and is processed as a one-dimensional array.

Example: Accessing an Element

You want to read the j-th element of a list P.

The algorithm requires knowing the number of items in the list (its length, L). The steps to be taken are:

Knowing the length of the list L.
If L = 0, display ‘error: empty list’. Otherwise, check if the j-th element is within the permissible range of elements 1 <= j <= L. In this case, assign the value of the element P(j) to a variable B. Note: if the j-th element is not within the range, display an error message “requested item does not exist in the list.”
End.

The corresponding pseudocode is:


Access procedure (E list: p; elementolista S: B, E integer: L, J)
Home

If L = 0 then
  Write (List empty)
Else
  If (j >= 1) and (J <= L) then
    B := P(J)
  Else
    Writing (error: no element exists)
  End If
End If
end

Deleting an Element

Deleting an element j in the list p.

Variables:

L: length of the list
J: position of the element to delete
I: subscript of the array P
P: list

The operations involved are:

See if the list is empty.
Check if the value of J is in the range of the subscript I to Schedule 1 <= J <= L.
If correct, move j+1 elements, j+2, …, to positions j, j+1, …, respectively, which will have erased the old element j.
Decrement by one the value of the variable L, as the list will now contain L – 1 elements.

Algorithm:


home
if L = 0 then
  write ('empty list')
else
  read (J)
  if (J >= 1) and (J <= L) then
    since I := J to make L-1
      P[I] := P[I + 1]
    f in from
    L := L - 1
  else
    write ('Element not exist')
  end if
end if

A contiguous list is one in which elements are adjacent in memory or support addressability. It has left and right limits or lower/upper bounds that cannot be discounted when adding an element.

Dynamic vs Static Data Structures: Linear Lists Explained