Welcome!
1. Welcome!
Welcome! I'm Miriam Antona, and I'll be introducing you to data structures and algorithms in Python.2. The importance of algorithms and data structures
Data structures and algorithms enable us to solve everyday problems using efficient code. This course is in Python, but it could be taught in any programming language.3. Algorithms and data structures
Let's start by defining some concepts. Algorithms are a set of instructions given to a computer to solve a problem. First, we design them; then, we code them in a programming language. Data structures hold and manipulate data when we execute an algorithm. We will build some advanced data structures, like linked lists, stacks, and queues.4. Linked lists
The data structure we will cover in this video is called a linked list. A linked list is a sequence of data connected through links.5. Linked lists - structure
Each element is called a node and has two parts.6. Linked lists - structure
The first part is the data. The second part7. Linked lists - structure
is a pointer8. Linked lists - structure
to the next node.9. Linked lists - structure
The last link10. Linked lists - structure
points to null.11. Linked lists - structure
The first node is the head,12. Linked lists - structure
and the final node is the tail. This data doesn't need to be stored in contiguous blocks of memory, so it can be located in any available memory address.13. Singly linked lists
If each node has one link, it is called a singly linked list. If each node14. Doubly linked lists
has two links in either direction, it is called a doubly linked list. We'll focus on singly linked lists.15. Linked lists - real uses
Linked lists can be used to implement other data structures like stacks, queues, and graphs. A common application of a linked list is to access information by navigating backward and forward, such as on a web browser or music playlist.16. Linked lists - Node class
Let's implement a node with a class. We start by defining the init method. Every time a class is instantiated, the init method is called. Here, init creates two attributes, data and next. data contains the value for the node, and next points to the next node. Initially, next will point to None.17. Linked lists - LinkedList class
We'll create another class called LinkedList, which will eventually contain nodes. Initially, there won't be any node at the head or the tail.18. Linked lists - methods
We can implement methods to insert or remove a node at the beginning, end or given position of a LinkedList, or to search for a value in the list.19. Linked lists - insert_at_beginning
Let's implement a method to add a new node at the beginning of a LinkedList.20. Linked lists - insert_at_beginning
First, we create the new_node. We check if the linked list is empty by checking if there is a head node. If there is,21. Linked lists - insert_at_beginning
new_node points to it,22. Linked lists - insert_at_beginning
and new_node becomes the head.23. Linked lists - insert_at_beginning
If the linked list is empty, new_node is both the head and tail.24. Linked lists - insert_at_end
Now that we know how to insert a node at the beginning of a linked list, let's implement a method to insert a new node at the end. If the list is not empty, the next node of the tail will be the new_node, and the new_node will become the tail. If the linked list is empty, the new_node will become both the head and tail.25. Linked lists - search
The last method we cover searches for a given value in a LinkedList. We initialize current node to the head. As long as we have nodes to visit, we check if their data is equal to the data we are searching for, returning True if it is,26. Linked lists - search
or updating current_node27. Linked lists - search
until we find it. We return False if we don't eventually find the data.28. Linked lists - example
With these three methods, we can build a new Linked_List and add nodes29. Linked lists - example
at the end,30. Linked lists - example
at the beginning,31. Linked lists - example
or search for a value.32. Let's practice!
Let's practice!Create Your Free Account
or
By continuing, you accept our Terms of Use, our Privacy Policy and that your data is stored in the USA.