What Is a Linear Data Structure?

In computer programming, a linear data structure is any data structure that must be traversed linearly. Examples of linear data structures include linked lists, stacks and queues.

For example, consider a list of employees and their salaries. Because there are two pieces of data per item (name and salary), an array is not useful for this type of data. One option for representing this data is a linked list with elements such as {Bob, 50000, next}, {Stacy, 75000, next}, {Tish, 200000, next}, {null}. The data between each set of curly braces corresponds to one element of the list, and “next” is a pointer to the next element of the list. To find an element in the list, write a function that follows the pointers through the list and searches for a name match. If it finds a match, report the corresponding salary. If the search function makes it all the way to the {null} element, the search has failed and the function should report an error.