Topic 3 – Basic Data Structures
Introduction
There are some structures that you will use a lot. If you paid attention to Topic- Algorithm and Programming then you know that the implementation of algorithms and structures should be a black box. You simply need to know about the Interface of the structure and you can use it and not worry about the exact implementation. However, as a programmer who is concerned about efficiency and space – you will care about which structure you use for a certain purpose. Also for this class – you need to know a little more about the inside of the black box. Let’s look at the most common data structure used by programmers – the List.
This page is a synopsis of the materials presented in wikibook – https://en.wikibooks.org/wiki/Data_Structures/List_Structures that gives a full and complete coverage of lists. You will be responsible for understanding, creating, and uses of Lists.
The List
We can define the interface of the list with the following capabilities. It is the Interface which defines an object as a List, if it has expected behavior to the defined interface – it is a List.
Create() – This could also be the contstructor.
Get(index) – Returns the element that is at the referenced location. Note that in this example it may look like we are assuming that the index is a number, this is not always true as we will see as we move to more complex lists.
Set(index, value) – Does exactly as you would expect, places the value at the passed index. Note that the syntax for the Get and Set may not be using Get and Set. For example the Array which is a List typically uses a syntax like A[index] to get the value and A[index] = value to set a value.
Insert(index, value) – In the case of Set, the value is put at the given index, replacing any value that might have been there before. Insert moves existing values. Based on the pattern of the values moved – they may be simply slid backwards, but again this assumes an integer indexed sequential list, which may not be the case. Either way, Insert does not overwrite existing values.
Delete(index) – Does exactly what you might expect, deletes the value at the passed index, potentially moving the surrounding items if it is a list that would require that action.
Retrieve(index) – This is similar to a Get, but the Get typically assumes a single value at the index, Retrieve makes no such assumption and can be useful if there are multiple values at an index. The values are retrieved in a Retrieve action.
Search(value) – Think of Retrieve, but in this case you pass the value and get back the index (location) of the value.
Empty() – Returns a Boolean (true/false) based on whether the list is empty.
Full() – Same as empty it returns a Boolean, but this time whether the list is Full.
Count() – Returns the number of values in the list.
Length() – In fixed length lists, this can be different than count, since there can be empty indexes, and the logic must take this into account.
Traverse( start_index, end_index) – Returns all elements between the start and end indexes.
Destroy() – Pretty self explanatory, it destroys the list in memory.
As you can see the simple List, just got a whole lot more complex and it is going to get more complex when you start adding features like Sort and concepts like Sort Keys – which may change the actual sorting algorithm. So our lowly simple list just became a much more interesting data structure. Let’s look at some types of lists.
Examples
Example – An example of an implementation of a Linked List in Javascript – FULLY documented is at this link: Full Javascript Implementation of a Singly Linked List
Example – A very simple implementation of a Linked List that I wrote – with one method implemented (add) – http://jsfiddle.net/reaglin/1e543pbe/
Supporting Video
Video – Abstract Data Types – The List
All students should view this video to gain an understanding of the linked list and some of its uses.
Link – https://www.youtube.com/watch?v=RylFkxFazCk
Video – Implementing a Linked List in Javascript
This video covers the coding associated with an implementation of a Linked List. This is one of multiple ways to implement – students should look at different options and get a better understanding of how different implementations are optimized for different needs.
Link – https://www.youtube.com/watch?v=4rZasAEfJZg
Types of Lists
Here is some light reading for you and some list types that you will need to know, with a little reference to help you out. Note that this is not a comprehensive list of all list types, it is just a group of fundamental lists that you should have some familiarity of the structure of the List. Also you should know about the time and space complexity of the lists that you may select for a different applications.
| Name of List Type | Information About List Type |
| Array | You should be familiar with this one |
| ArrayStack | http://www.opendatastructures.org/ods-python/2_Array_Based_Lists.html |
| ArrayDeque | http://www.opendatastructures.org/ods-python/2_Array_Based_Lists.html |
| DualArrayDeque | http://www.opendatastructures.org/ods-python/2_Array_Based_Lists.html |
| RootishArrayStack | http://www.opendatastructures.org/ods-python/2_Array_Based_Lists.html |
| Singly Linked List | http://www.opendatastructures.org/ods-python/3_1_SLList_Singly_Linked_Li.html |
| Doubly Linked List | http://www.opendatastructures.org/ods-python/3_2_DLList_Doubly_Linked_Li.html |
| Space Efficient Linked List | http://www.opendatastructures.org/ods-python/3_3_SEList_Space_Efficient_.html |
| SkipList | http://www.opendatastructures.org/ods-python/4_Skiplists.html |
Other Data Structures
We will be moving on to other data structures in upcoming topics, many of these build on top of the concept of a List, but add different capabilities. Also it is worth noting that when we look at time complexity O(n) of different List implementations for different operations we get different values. So in selecting the type of list you want to use in your programming – you just don’t randomly select one type of list – but instead look at the how the list will be used.