Lecture 5: Data Structures

Structures (structs)

“super variable” that provides a way to unify several variables of different types into a single, new variable type which can be assigned its own type name.

Arrow Operator (→)

an operator that does two things back-to-back: First, it dereferences the pointer on the left side of the operator. Second, it accesses the field on the right side of the operator.

Linked List Node

a special kind of struct with two members: Data of some data type (int, char, float…) and A pointer to another node of the same type

Linked List

a type of data structure that combines the use of pointers, dynamic memory allocation, and structs which gives the ability to grow and shrink a collection of like values to fit our needs.

Create a Linked List

Search through a linked list to find an element.

Insert a new node into the linked list (singly)

Delete an entire Linked List

Difference between a Singly-Linked List and a Doubly-Linked List

a singly linked list can only ever move in one direction through the list while a doubly linked list allows us to move forward and backward through the list, all by simply adding one extra pointer to our struct definition

Insert a new node into a linked list (doubly)

Delete a node from a linked list.

Benefit of using Linked Lists

supports extremely efficient insertion and deletion of elements (operations are done in constant time)

Downfall of using Linked lists

lost the ability to randomly-access list elements (accessing a desired element now takes linear time)

Stack

a special type of structure that can be used to maintain data in an organized way and is commonly implemented as an array or a linked list (follows LIFO)

Last in, first out (LIFO)

important rule of a stack; when data is added to the stack, it sits “on top,” and so if an element needs to be removed, the most recently added element is the only element that can legally be removed.

Push

Stack operation that adds a new element to the top of the stack.

Pop

Stack operation that removes the most recently-added element from the top of the stack

Array based implementation of a stack

Use of push() in a array-based implementation of a stack

Use of pop() in a array-based implementation of a stack

Linked List-based implementation of a stack

Use of push() in a linked list-based implementation of a stack

dynamically allocate a new node, set its next pointer to point to the current head of the list, then move the head pointer to the newly-created node.

Use of pop() in a linked list-based implementation of a stack

traverse the linked list to its second element (if it exists), free the head of the list, then move the head pointer to the (former) second element

Queue

a special type of structure that can be used to maintain data in an organized way and is commonly implemented as an array or a linked list (follows FIFO)

FIFO

Important Rule of a queue; when data is added to the queue, it is tacked onto the end, and so if an element needs to be removed, the element at the front is the only element that can legally be removed.

Enqueue

Queue operation that adds a new element to the end of the queue.

Dequeue

Queue operation that removes the oldest element from the front of the queue.

Array-based implementation of a queue

Use of enqueue() for a Array-based implementation of a queue

Use of dequeue() for a Array-based implementation of a queue

Linked List-based implementation of a queue

Use of Enqueue() in a Linked List-based implementation of a queue

Use of dequeue() in a Linked List-based implementation of a queue

Usefulness of Hash tables’ ability to combine the random access ability of an array with the dynamism of a linked list.

downfall is that they are not great at ordering or sorting data,

Hash table consists of..

1. a hash function, which returns an nonnegative integer value called a hash code.

2. an array capable of storing data of the type we wish to place into the data structure.

A good hash function should..

Collision

occurs when two pieces of data, when run through the hash function, yield the same hash code

Linear probing

a method to solve collisions where if we have a collision, we try to place the data in the next consecutive element in the array (wrapping around to the beginning if necessary) until we find a vacancy. That way, if we don’t find what we’re looking for in the first location, at least hopefully the element is somewhere nearby.

Clustering

a possible problem of linear probing where once there’s a miss, two adjacent cells will contain data, making it more likely in the future that the cluster will grow.

Chaining

a method to solve collisions where instead of each element of the array holding just one piece of data, it held multiple pieces of data (If each element of the array is a pointer to the head of a linked list, then multiple pieces of data can yield the same hash code and we’ll be able to store it all)

Trie

combines structures and pointers together to store data in a roadmap (no collisions and no two pieces of data (unless identical) have the same path)

Array Summary

Linked List Summary

Hash Table Summary

Tries Summary