Data Structures arrays, linked lists, and hash tables PDF

Preview

Summary

I can't find anything useful in the slides, but if you can add a bit more information, I can probably help you out.
The problem I have with the slides is that I don't understand them.
I'm a beginner too.



There is a book called "Introduction to Algorithms" by Co...

Description

Data Structures arrays, linked lists, and hash tables

Main concepts:

Diffrent serach algoritims Binary Search Linear Search

BigO relating to lists

BigO for list operations, insert, delete, search

Abstract data types

Linked list single linked list doubly linked list

maps list based maps

key indexed arrays

Hash tables

understand remaining slides

Array Data Structure Tutorial - Array Time Complexity This data structure tutorial covers arrays. It discusses the time complexity of operations such as adding and removing elements as well as indexing items. An...

https://www.youtube.com/watch?v=B2KusJcbVIg Data Structure and Algorithms - Hash Table Hash Table is a data structure which stores data in an associative manner. In a hash table, data is stored in an array format, where each data value has its own unique index value. Access of data becomes very fast if we know the index of the desired data. https://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm Hash table - Wikipedia In computing, a hash table ( hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found. https://en.wikipedia.org/wiki/Hash_table

What is an array?

An array is a set of memory locations that can be addressed using consecutive indices

What can arrays store?

What is the running time for an array?

constant time O(1)

What is Linear Search?

We are searching through a list one by one and checking if it matches the target element

What is Binary Search?

First, we need a sorted array.

Then we compare the target element to the midpoint

If the target element is higher or lower. We move to lefthand if its lower or righthand side if its higher.

Then we remove elements that were too high or low for the target element. And create a new midpoint. And start the process again.

What is the time complexity of Linear Search?

The worst case complexity is O(n)

What is the time complexity of Binary Search?

O(log n)

Prove why ___ is the time complexity of binary search?

How does memory allocation work in an array?

The address of a[i] can be determined out arithmetically by adding a suitable offset to the address of the head of the array AND the array is still contiguously in memory

What are the 3 fundamental algorithms when dealing with data structure?

Search: O(n) or O(log n),

Insert: O(1) or O(n)

Delete: O(1) or O(n)

What are Abstract data types?

Abstract data types separate the specification (what kind of data we're working with, and what operations can be performed on it) and implementation (how is data and operations can actually be implemented)

Benefits of Abstract data types

Code is easier to understand (being able to see “high level” steps being performed, not obscured by low-level code or “clutter”)

Implementations of ADT can be changed (e.g for efficiency) without requiring changes to the program that uses ADT

ADT can be reused for future program

What are the two types of ADTs?

What is a linked list?

A linked list is based on the concept of a self-referential object - an object that refers to an object of the same class

What is a singly linked list?

Explain how to insert an element linked list head?

Explain how to remove at the head of the linked list?

Explain how to insert at the tail?

Explain how to insert inside the list?

What is a Doubly linked list?

Explain insertion in a Doubly linked list? [improve answer]

Explain deletion in a Doubly-linked list? [improve answer]

what is the time complexity of a doubly linked list? Search: O(n) Insertion: O(n) Deletion: O(n)

What is a map?

A map models a searchable collection of key-value entries

Main operations of a map?

The main operations of a map are for searching, inserting, deleting items (seen with linked lists)

What is a list based map?

key-index array

What are hash tables?

Hash tables are data structures that save abstract data types in an associative manner.

What is hashing?

Hashing is a technique to convert a range of key values into a range of indexes of an array.

What are collisions?

Collisions are when an index already has a stored value.

How to deal with collisions?

The most common solutions are: Chaining (Linked list) Linear Probing

How does Chaining work in a hash table?

We store a linked list, where are multiple values mapped into index. Then we use the key to nagivate the linked list

How does Linear probing work?

As we can see, it may happen that the hashing technique is used to create an already used index of the array. In such a case, we can search the next empty location in the array by looking into the next cell until we find an empty cell. This technique is called linear probing.

Wikipedia definition:

When the hash function causes a collision by mapping a new key to a cell of the hash table that is already occupied by another key, linear probing searches the table for the closest following free location and inserts the new key there. Lookups are performed in the same way, by searching the table sequentially starting at the position given by the hash function, until finding a cell with a matching key or an empty cell.

How do you insert an element in a hash table?

Whenever an element is to be inserted, compute the hash code of the key passed and locate the index using that hash code as an index in the array. Use linear probing for empty location, if an element is found at the computed hash code.

How to find an element in a hash table?

Whenever an element is to be searched, compute the hash code of the key passed and locate the element using that hash code as index in the array. Use linear probing to get the element ahead if the element is not found at the computed hash code.

How do you delete an element in a hash table?

Whenever an element is to be deleted, compute the hash code of the key passed and locate the index using that hash code as an index in the array. Use linear probing to get the element ahead if an element is not found at the computed hash code. When found, store a dummy item there to keep the performance of the hash table intact.

What is Closed bucket hash table

What is an Open bucket hash table?

What is a hashing algorithm?

Hashing algorithms are a class of hash functions that allow you to quickly search through a large table of data, so you don’t have to scan every element.

What are the three hashing algorithms?

-linear probing -Quadratic probing -Double hashing

What is the time complexity of a hash table?

What is the time complexity of an array?

What is the running time of an array?

What is...