Data structure
Data structure is a specialized means of organizing and storing data in computers in such a way that we can perform operations on the stored data more efficiently
Algorithm
is a step-by-step procedure for solving a problem in a finite amount of time with finite amount of effort(resources).
What is an efficient algorithm :One whose function's values are small, or grow slowly compared to a growth in the size of the input.
Types of Data structure
Python has implicit support for Data Structures which enable you to store and access data. These structures are called list , Dictionary , sets and tuples
Python also allows its users to create their own Data Structures enabling them to have full control over their functionality . The most prominent Data Structures are
Stack,Queue, Tree, Linked List , graph **and **hash tables .
1. List
To represent a sequence of items indexed by their integer position, one data structure you can use is a list. Lists contain zero or more elements and can contain elements of different types. List is a mutable ordered sequence of element mutable meaning that you can add, delete, or change elements in a flexible manner
Access list items:
List elements are accessed by the assigned index.Starting index of the list is 0 and the ending index is n-1 where n is the number of elements.
students[0] _gets the first element in a list
_students[0] = ‘Amina' changes a list item by offset.
students[0:2] _slices to extract items by offset. This example returns the first 2 elements of students.
Add list items:
_append() _adds an item to the end of a list.
_extend() or += merges one list into another.
insert() adds an item before any offset.
Remove list items:
remove() removes an item value from a list.
pop() removes the last (or specified) element while also returning the value.
del removes an item by its position in the list. del is a Python statement, not a list method.
join() returns a string of combined list items. The argument for join() is a string or any iterable sequence of strings.
_len() _returns the number of items/length in the list.
_count() _returns the number of occurrences of a specified value.
#defining a list students = ['sam', 'pam', 'rocky', 'austin', 'steve', 'banner'] #acessing element in a list print(students[0]) print(students[-3]) print(students[1:3]) #adding element in a list students.append("amina") print(students) #deleting element in a list students.pop(0) print(students) #printing the len of the list print(len(students)) #join string in a list name = "-".join(["Jack", "O", "Lantern"]) print(name) output: sam austin ['pam', 'rocky'] ['sam', 'pam', 'rocky', 'austin', 'steve', 'banner', 'amina'] ['pam', 'rocky', 'austin', 'steve', 'banner', 'amina'] 6 Jack-O-Lantern 2 Dictionaries
Instead of using an offset, dictionaries use keys to associate with each value. This means that order is not tracked and should not matter if you plan to use a dictionary. Dictionary keys are immutable and unique, however, dictionaries are mutable; the key-value elements can be added, deleted, or changed
Create dictionaries using {}. Typecast using dict()
Access value in dictionary
book[‘key’] gets an item by its key
*Updating value in a dictionary *
book['key'] = ‘value' _uses a key to add (or change if it already exists) a value.
_update() merges the keys and values of one dictionary into another.
*Removing value in a dictionary *
del deletes an item by the provided key. del is a Python statement, not a dictionary method.
keys() returns all the dictionary keys. values() returns all the values in the dictionary. items() returns all the dictionary key-value pairs.
# dictionaries help us store complicated data, which is not single valued like a number or a string book = { 'title': "How to be awesome", 'author': "john doe", 'isbn': "1234-23-15-12-3", 'date_published': "23-21-2010", 'year': 2010} # access value in a dict book_title = book['title'] print(book_title) # update value in a dict book['title'] = "2020 what went wrong" print(book["title"]) # get all the keys in this dictionary keys = book.keys() print(keys) #deleting item from dictionary del book['isbn'] print (book) #adding item to dictonary book['page']=450 print(book) #Checking if a Key exists if "year" in book: print("Yes, the keyword exists in the dictionary") else: print('No, the keyword does not exist in the dictionary') output How to be awesome 2020 what went wrong dict_keys(['title', 'author', 'isbn', 'date_published', 'year']) {'title': '2020 what went wrong', 'author': 'john doe', 'date_published': '23-21-2010', 'year': 2010} {'title': '2020 what went wrong', 'author': 'john doe', 'date_published': '23-21-2010', 'year': 2010, 'page': 450} Yes, the keyword exists in the dictionary 3 Tuples
Tuples are also a sequenced data structure, just like lists. However, tuples are immutable; you cannot add, delete, or change items after a tuple is created. Tuples differ from lists by having many fewer functions because they can’t be modified after being defined. Tuples contain zero or more elements and can contain elements of different, immutable types
Create tuples using () or a comma-separated list of elements with no surrounding brackets or braces. Typecast using tuple().
Accessing element in a tuples
Accessing items in a tuple is similar to a list, we can access elements in a tuple using indexes. We can specify the index value and it will return the item stored at that particular index value.
Concatenating two tuples
vector = (4, 5, 9) #acessing element in a tuple print("x-coordinate:", vector[0]) print("y-coordinate:", vector[1]) print("z-coordinate:", vector[2]) location = 108.7774, 92.5556 latitude, longtitude = location print("The coordinates are {} x {}".format(latitude, longtitude)) output: x-coordinate: 4 y-coordinate: 5 z-coordinate: 9 The coordinates are 108.7774 x 92.5556 4.Sets
A set is like a dictionary with only the keys, not the values. This means that sets are unique and not sequential. Sets are also mutable. Sets contain zero or more elements and can contain elements of different, immutable types .Create sets using set(). Typecast using set().
Operation that can be done in a list
add() adds an item to the set if it doesn’t already exist
remove() removes specified items from the set
intersect() returns an intersection of two sets
union() returns a union of two sets
set ={1,2,5, "amina"} print(set) #acessing item in a set for x in set: print(x) #add item in a set set.add("sandra") print(set) #deleting element in set set.remove("amina") print(set) output: {1, 2, 5, 'amina'} 1 2 5 amina {1, 2, 5, 'sandra', 'amina'} {1, 2, 5, 'sandra'} 5. Stack
Stack are linear Data Structures which are based on the principle of Last-In-First-Out (LIFO) where data which is entered last will be the first to be accessed. It is built using the array structure and has operations namely, pushing (adding) elements, popping (deleting) elements and accessing elements only from one point in the stack called the TOP. This TOP is the pointer to the current position of the stack.example :5 is added in to the stack ontop of 4 and while removing you have to start with the top most element which 5 is removed first followed by 4 thus the term Last-In-First-Out .
Operation done in stack
empty()– Returns whether the stack is empty.
size() – Returns the size of the stack.
top()– Returns a reference to the topmost element of the stack.
push()– Inserts the element ‘a’ at the top of the stack.
pop() – Deletes the topmost element of the stack.
# implementing stack using List : myStack = [] #adding item to the stack myStack.append(10) myStack.append(100) myStack.append(1000) myStack.append(10000) print("Initial stack is:",myStack) #removing utem form the list print(myStack.pop()) print(myStack.pop()) print(myStack.pop()) print("After Removing elements:",myStack) output: Initial stack is: [10, 100, 1000, 10000] 10000 1000 100 After Removing elements: [10] 6. Queues
A queue is also a linear data structure which is based on the principle of First-In-First-Out (FIFO) where the data entered first will be accessed first. It is built using the array structure and has operations which can be performed from both ends of the Queue, that is, head-tail or front-back. Operations such as adding and deleting elements are called En-Queue and Dequeue and accessing the elements can be performed.
Operation performed in queues
enqueue(): Adds an element to the back of queue Q..
dequeue(): Removes and returns the first element from queue Q. Error occurs if empty.
empty(): Returns True if no elements found in queue Q, else returns False
size(): Returns the number of elements in queue Q.
# implementing Queue using List : queue=[] queue.append(10) queue.append(100) queue.append(1000) queue.append(10000) print("Initial Queue is:",queue) print(queue.pop(0)) print(queue.pop(0)) print(queue.pop(0)) print("After Removing elements:",queue) output Initial Queue is: [10, 100, 1000, 10000] 10 100 1000 After Removing elements: [10000] 7.Linked list
A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers.
Operation performed in linked list
Traversal: To traverse all the nodes one after another.
Insertion: To add a node at the given position.
Deletion: To delete a node.
Searching: To search an element(s) by value.
# A single node of a singly linked list class Node: # constructor def __init__(self, data = None, next=None): self.data = data self.next = next # A Linked List class with a single head node class LinkedList: def __init__(self): self.head = None # insertion method for the linked list def insert(self, data): newNode = Node(data) if(self.head): current = self.head while(current.next): current = current.next current.next = newNode else: self.head = newNode # print method for the linked list def printLL(self): current = self.head while(current): print(current.data) current = current.next # Singly Linked List with insertion and print methods LL = LinkedList() LL.insert("Lux ") LL.insert("Tech") LL.insert("Academy") LL.printLL() output: Lux Tech Academy 
Top comments (0)