Every program must deal in some way with data. There are many ways of storing data, often referred to in programming as data structures. Arrays and linked lists are only two types of data structures, each having its own distinct properties and potential uses.
What Is an Array?
Typically, an array is used to house a list of values such as list of publications, brands of automobiles, schools in a district, or other reasonably static objects.
Arrays are a special kind of object. Use arrays when you want element names using numbers, and objects when elements with text string names are preferred.
Creating an array is executed easily using an array literal which provides the array name as well as the items included in the array, as in this example:
Var presidents = [“Madison”, “Washington”, “Lincoln”]
The list of elements can contain as many entries as needed.
Using an Array
Some of the strengths of arrays are their very properties and methods of use:
How do you add elements to an array? A simple ‘push’ option creates a new entry in the array.
Removing an element is accomplished through a ‘pop’ option.
- Shift – removes the first entry in the array, shifting the remaining elements to a lower index
- Delete – with a specified index – changes that element to undefined
- Splice – can be used to remove elements of the array
- Concat (concatenate) – create a new array from merging arrays that already exist
- Slice – create a new array from portions of another array
- Sort – arrays may be sorted in ascending or descending sequences
What Is a Linked List?
A linked list is a data structure that is linear in nature, with a ‘head’ preceding the first data element, and each element containing a reference to the next element, referred to as the ‘node’.
The last node or element of a linked list has a null reference. How do you know if the linked list is empty? If there are no elements, the head contains a null value.
Are There Multiple Types of Linked Lists?
Yes – there are variations of linked lists:
- The linked list described above is known as a ‘singly’ linked list
- A doubly linked list has two references – one to the next node, and one to the previous node
- A circular linked list contains a reference on the last node or element that points back to the head of the list (first node).
Coding options to process a linked list include:
- addFirst – insert an element at the beginning of the list (the new node becomes the head, and its reference points to the element that was previously the first element)
- addLast – add a new node at the end of the list
- insert (After or Before) – creates a new entry in the list, either before or after a node
Nodes can also be changed or deleted from a linked list easily.
Linked List vs Array
Since arrays are indexed, adding or removing an element of the array means each of the following elements must be re-indexed. This can be a significant performance issue for large arrays where thousands of elements are involved. This is why linked lists are most often the appropriate choice for such applications.
Need screaming performance? Arrays are typically stored in blocks of memory that are contiguous (in array cache), making them high performers. Larger linked lists could require more time to access the nodes being referenced.
Linked lists are accessed sequentially through the processing of node references, possibly slowing performance in accessing individual data nodes. Arrays, however, can be accessed directly by index.
Making the decision whether to utilize a linked list vs. array depends on the performance needed, the access method you will use in retrieving the data, and the sheer volume of data elements to be included in the data structure.