| 
  • If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • Stop wasting time looking for files and revisions. Connect your Gmail, DriveDropbox, and Slack accounts and in less than 2 minutes, Dokkio will automatically organize all your file attachments. Learn more and claim your free account.

View
 

Topic - Basic Data structures

Page history last edited by Dr. Ron Eaglin 3 years ago

Topic - Basic Data Structures

 

Introduction

 

There are some structures that you will use a lot.  If you paid attention to Topic - Algorithms 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

 

Understanding the Linked List as an Abstract Data Type

 

All students should view this video to gain an understanding of the linked list and some of its uses.

 

 

 

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.

 

 

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 

http://en.wikipedia.org/wiki/Dynamic_array 

Singly Linked List

http://www.opendatastructures.org/ods-python/3_1_SLList_Singly_Linked_Li.html 

http://en.wikipedia.org/wiki/Linked_list 

Doubly Linked List

http://www.opendatastructures.org/ods-python/3_2_DLList_Doubly_Linked_Li.html 

http://en.wikipedia.org/wiki/Linked_list 

Space Efficient Linked List

http://www.opendatastructures.org/ods-python/3_3_SEList_Space_Efficient_.html 

http://en.wikipedia.org/wiki/Linked_list 

SkipList

http://www.opendatastructures.org/ods-python/4_Skiplists.html 

http://en.wikipedia.org/wiki/Linked_list 

http://en.wikipedia.org/wiki/Skip_list

 

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.

 

Comments (0)

You don't have permission to comment on this page.