Jennifer Bland header image
≡ Menu

Data Structures – Linked List, Set and Hash Table

A data structure is a particular way of organizing data in a computer so that it can be used efficiently.  Previously I talked about two very similar data structures - tree and graph. Today I am going to talk about Linked Lists, Sets and Hash Tables.

There are many different types of data structures simply because each one provides certain benefits over the others. One may be better at retrieving data, another might be better at inserting data and yet another might be better in its ability to expand as the size of the data increases.

Linked List

Linked lists are among the simplest and most common data structures.  In a linked list each node has a value and a pointer to the next node in the data structure.

linked list

 

The principal benefit of a linked list over a conventional array is that the list elements can easily be inserted or removed without reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory or on disk, while an array has to be declared in the source code, before compiling and running the program.

Linked lists allow insertion and removal of nodes at any point in the list, and can do so with a constant number of operations if the link previous to the link being added or removed is maintained during list traversal.

A linked list data structure typically will have a head and a tail that point to the start and end of the data structure.

Generally you will have an addToHead() and addToTail functions that will insert new items at the beginning or end of the data structure.

To remove items there will be generally a removeHead() and a removeTail() functions.

To see if a linked list contains a value you will have a contains() function that will return true if the linked list contains the value or else returns false.

Set

A set is an abstract data type that can store certain values, without any particular order, and no repeated values. Unlike most other collection types, rather than retrieving a specific element from a set, one typically tests a value for membership in a set.

Set data structure

Sets can be implemented using various data structures, which provide different time and space trade-offs for various operations.

Since there is no particular order in a set, to implement one you only need to have an add() and remove() functions.

You should also provide a contains() function to return whether or not an item is contained in the set.

Hash Table

A hash table is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the correct value can be found.

hash table

Ideally, the hash function will assign each key to a unique bucket, but it is possible that two keys will generate an identical hash causing both keys to point to the same bucket.

In a well-dimensioned hash table, the average cost for each lookup is independent of the number of elements stored in the table. Many hash table designs also allow arbitrary insertions and deletions of key-value pairs, at constant average cost per operation.

In many situations, hash tables turn out to be more efficient than search trees or any other table lookup structure.

by Jennifer Bland

I am a Google Developers Expert. Entrepreneur. Mountain Climber. Neil Diamond fanatic. World traveler. MBA grad. Software Engineer. Interested in hiring me? Contact me at ratracegrad@gmail.com

0 comments… add one

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.