Choosing data structures

The selection of data structures used in a program depends on both the type of data being stored and the operations the program may need to perform on that data. Choosing the best data structure often requires determining which data structure provides a good balance given expected uses. Ex: If a program requires fast insertion of new data, a linked list may be a better choice than an array.

PARTICIPATION ACTIVITY

$2\mathrm{.}1\mathrm{.}2$: A linked list avoids the shifting problem.

Start

Insert B

A

C

W

B

linked list:

array:

A

C

B

W

$0$

$1$

$2$

$3$

Insert B

Static figure:

Pictured are an array and a linked list. Each data structure is accompanied by the text "Insert B$".$

The array has these elements in this order: A$,$ B$,$ C$,$ W$.$ Each of these four elements is numbered according to its position in the array; that is$,$ A is numbered $0,$ B is numbered $1,$ C is numbered $2,$ and W is numbered $3.$

The linked list has the same four elements in the same order: A$,$ B$,$ C$,$ D$.$ The node containing element $"$A$"$ has an arrow pointing down$-$right to the node with element $"$B$",$ which has an arrow pointing up$-$right to the node with $"$C$",$ which has an arrow pointing right to the last node with $"$W$".$

Step $1$: Inserting an item at a specific location in an array requires making room for the item by shifting higher$-$indexed items.

Array with contents $[$A$,$ C$,$ W$]$ appears, with the elements numbered $0,1,2$ respectively. The text "Insert B$"$ also appears. In the array, an empty slot appears to the right of the slot containing element W and is numbered $3.$ W and C each shift $1$ position to the right to make room for a new array entry at index $1.$

Step $2$: Once the higher index items have been shifted, the new item can be inserted at the desired index.

The $"$B$"$ from the text "Insert B$"$ replicates and the replica moves to the now empty slot in the array at index $1.$ The array thus contains these elements: A$,$ B$,$ C$,$ W

Step $3$: To insert a new item in a linked list, a list node for the new item is first created.

A linked list appears with nodes, each node having one element. The node containing element $"$A$"$ points to the node containing element $"$C$",$ which points to the node containing element $"$W$".$ A new node appears that contains element $"$B$".$

Step $4$: Item B$\text{'}$s next reference is assigned to reference item C$.$ Item A$\text{'}$s next reference is updated to reference item B$.$ No shifting of other items was required.

An arrow appears that points from the node with element $"$B$"$ to the node with $"$C$"$; then, the arrow pointing from the node with element $"$A$"$ to the node with $"$B$"$ moves such that it now points to the node with element $"$B$".$

Captions

Feedback