2016-03-27-data-structure-basics-3.md 6.0 KB
title: Data Structure Basics pt.3 description: > Notes on lists. categories: posts
tags: [data-structures, ruby]
Table of Contents
- TOC {:toc}
Review
Previously we talked about data structures in general{:rel="noopener"}. Then we focused on arrays{:rel="noopener"}. Now it's time to cover lists, stacks, and queues.
Lists
A list, like an array, is a kind of collection. That is because they both group items together under one name. The main difference between traditional arrays and traditional lists is in the idea of direct access vs sequential access. This has to do with the way they are stored in memory. Another difference is in vocabulary. Whereas arrays contain data objects, lists contain nodes. Nodes are nothing but the data object plus one or more pointers. Pointers hold references to other nodes.
Direct Access
We say that a data structure supports direct access when all of its elements are allocated next to each other in memory. Arrays support direct access. That means that as long as we know the index of an item we can find it almost instantly regardless of the array's size.
Sequential Access
Just like arrays are all about direct access, lists are all about sequential access. Lists are collections of ordered items whose structure instead of being based on an strict numeric index is based on a sequence of elements which don't have to be stored in memory next to each other.
Linked Lists
The sequence, or order, of a linked list is manage by each node. Nodes keep references to nodes connected to them.
Singly Linked Lists
The nodes in this kind of lists only hold the reference to the next node. Typically the last node's next-reference leads to Null.
- Singly linked list{:rel="nofollow noopener noreferrer"}
Doubly Linked Lists
Nodes in doubly linked lists hold references to both, the previous and next nodes. This makes inserting and removing nodes a simpler task. Just like with singly linked lists the last node's next-reference leads to Null and so does the first node's previous-reference.
- doubly linked list{:rel="nofollow noopener noreferrer"}
Circular Doubly Linked Lists
The main difference between circular and common doubly linked lists is that instead of having the first and last nodes point to Null, we point them at each other. That is, the first node's previous-reference points to the last element of the list. Likewise, the last node's next-reference points to the first node.
- circular doubly linked list{:rel="nofollow noopener noreferrer"}
Lists in Ruby
Ruby doesn't have a built-in implementation.
Stacks
Stacks, like arrays and lists, are collections of items. The difference is
in the way they behave which is better described by the LIFO acronym; Last in,
first out, which is how regular stacks work.
Generally, stacks respond to three messages. push, to add to the top. pop, to
remove from the top only. peek, to check what the object at the top is
without removing it. Not all stacks implement the peek method.
- stack operations{:rel="nofollow noopener noreferrer"}
Working with stacks should be even simpler than working with arrays and linked lists because there is less we can do with it. It is intentionally limited.
Stacks in Ruby
Even though Ruby doesn't have a built-in implementation for stacks we can loosely
emulate one with an array. Arrays in Ruby respond to #push and #pop the same
way stacks do. Keep in mind, though, that even when Ruby has a #peek method, it
doesn't behave as described above because ruby arrays are not stacks.
Queues
Whereas stacks are last-in-first-out, queues are first-in-first-out. This means that we can only add elements to the back of a queue, and we can only pick them from the front. Queues are important for multithreads. This is how we enqueue (add) items:
- enqueue{:rel="nofollow noopener noreferrer"}
Here's the diagram for dequeue (remove)
- dequeue{:rel="nofollow noopener noreferrer"}
Priority Queues
This kind of queues allow us to specify a priority to the elements as we add them to the queue. This way new objects can be added ahead of other already there. If we add several items with the same priority they should follow FIFO. Since defining priority can be tricky, we usually need to implement a comparison function where we can define what we consider a higher, lower, or equal priority.
Deque (Double-ended Queues)
This kind of queue allows us to add and remove objects from either end but never from anywhere else. Hence, a deque behaves like both a stack and a queue.
Queues in Ruby
Just like with stacks, Ruby doesn't have a built-in queue implementation. Yet,
we can use ruby arrays to get the same behavior as simple queues, as well as
deques. We use push for adding objects to the end of an array. And #shift for
picking the first object. If we need priority queues we need to implement them.
Do not confuse the queue behavior of an array with the Queue class which is meant to be used as a way to synchronize communication between threads (Ruby Thread objects).
Before We Go
In this short article we covered some of the most fundamental data structures. We also talked about how we can get similar behavior from Ruby's own array implementation. Which should proof extremely useful to built custom data structures. On the next article we'll talk about associative arrays. Cheers!