What Are Linear Data Structures? Dzone Big Data

Linked Lists
A linked list is a data structure where each item points to the next.
We can't jump to any element directly like we can with an
array. Instead, we have to access them in turn:
an image of a linked list
Linked lists are useful because, unlike an array, we don't need to
decide up-front how much space we need. If we need to add a new
item, we simply add it to the end.
That means that adding the 200th item has the same cost as adding
the 2nd item. This predictable performance is an advantage of a
linked list.
It's also easy to add or remove an item from the middle of the
linked list, by simply changing some 'next' pointers.
Here's how we'd remove an item from a linked list:
removing an item from a linked list
This would be more difficult to do in an array, as we'd have to shift
all of the remaining items to account for the new or removed item.
A variant of the linked list is the 'doubly-linked list', where each
element not only points to the next element, but also the previous
one.
This means we can traverse the data structure in either order, but
still have the advantages of a linked list.
an image of a doubly-linked list
Queues
The queue is a 'First In First Out' (FIFO) data structure. That means
that items are read in the same order that they are inserted.
This is just like the queue at the store, the first person to join the
queue is the first person to be served.
an image of a queue
A printer queue is a good example of this data structure in use. The
printer will print items in the order in which they were queued. If
you send your document to the printer last, it will be the last thing
to be printed.
Queues are also useful as 'buffers'.
Suppose we have two separate systems, one that reads messages
and one that processes them. We don't want the system that reads
messages to have to wait for each message to be processed before
listening for another.
Putting a queue between them allows us to 'de-couple' those
systems. The read process can keep adding items to the queue, safe
in the knowledge that the processing side will pull the items off of
the queue and process them eventually - no waiting required.
Stacks
The stack is a 'Last In First Out' data structure; the last item to be
added is the first item to be read.
You can think of this like a stack of plates, the last plate to be added
to the pile is the first plate we'd take off again:
an image of a stack
You might use a stack to implement 'undo' functionality, for
example. The last task the user performed is the first one to be
reversed when they click the 'undo' button.
The 'call stack' we see every day when running code is also a great
example of a stack, but that's a topic for a future newsletter!