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 part

7. Linked lists - structure

is a pointer

8. Linked lists - structure

to the next node.

9. Linked lists - structure

The last link

10. 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 node

14. 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_node

27. 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 nodes

29. 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

By continuing, you accept our Terms of Use, our Privacy Policy and that your data is stored in the USA.