02_linked_lists.md

Linked List

What to talk about

• Design of linked list (include image)
• How does it link to each other
• How does it save memory (uses space in memory instead of array of data)
• When to use it
• performance

 

Design of a linked list

A linked list is a list of values that are not stored in a specific array. Instead, the values are stored in memory
and are accesed by referencing the other values. In the image below, we think of a linked list as many nodes
or boxes, and each node has a value. The first node is the first value, and is then references the next value.
The first node is the head, or the first value. The last node in the list is the tail, or the end value.

The arrows in the image represent the references made between nodes. As you can see in this image, 10 is the head,
or the first value in the list. In this case, 10 is referencing 20 as the next value in the list. 20 is
referencing 10 as the previous value in the list, and 16 as the next value in the list. This goes on until the
last value. In this case, 15 is the last value in the list. 15 references 6 as the previous value, and
15 is set as the tail of the linked list.

 

 

How Do They Link Together?

Linked lists in our examples are going to be inside of classes to make it easier to work with and see.
First off, we'll define a Linked_list class, and define a head and a tail. Notice that we are not currently
assigning the head and tail any values, and that is because we don't have any values to input now.

 

class Linked_list:

    def __init__(self):
        self.head = None
        self.tail = None

 

Second, we are going to create that class to go inside of the Linked_list class. Here, we define a value,
a next and a previous value. The value will hold the value inside the linked list. The next will be the
reference to the next value in the list. The previous will do the same thing, but for the previous
value in the list.

 

class Linked_list:

    class Node:

        def __init__(self, value):
            self.value = value
            self.next = None
            self.previous = None

    def __init__(self):
        self.head = None
        self.tail = None

 

Adding All Values

• create linked list w/references to everything
• Create that iter function to run through list
• create function to sum all values (have them create that function)

 

# refer to list_ex1.py file for full code

class Linked_list:
   """
   Create a linked list that holds the values of the head and the tail. Any other data
   to be held here will be within the inner class Data.
   """

   class Data:
       """
       Here will be the values held in the list. There will also be references to 
       the next itmes in the linked list.
       """

       # define the values held and the references to the next item in the list
       def __init__(self, value):
       self.value = value
       self.next = None
       self.prev = None


   # define the head and tail of the linked list
   def __init__(self):
       self.head = None
       self.tail = None


   # function to insert into list
   # user will specify if the item is to be placed in head or tail (one function for two purposes)
   def insert(self, value, place):
       # create a var to store the new data
       # change the var name later
       stuff = Linked_list.Data(value)


       # if there is no data, set the head and tail as the new data
       if self.head is None and self.tail is None:
           self.head = stuff
           self.tail = stuff

       else:
           # if place is 'head'
           if place.lower() == 'head':
               stuff.next = self.head    # connnect the old head to the new data
               self.head.prev = stuff    # connect the previous head to the new data
               self.head = stuff         # set the head to the new data

           elif place.lower() == 'tail':
               stuff.prev = self.tail    # connect the old tail to the new data
               self.tail.next = stuff    # connect the previous tail to the new data
               self.tail = stuff         # set the tail to the new data

 

Storing Images Together

• Create a linked list
• Allow the user to type in the name of the image, along with the alt text

 

For the coding assignment, I would like you to do the following:

1. Create a linked list
2. Allow the user to type in and store images in the list (or image paths)
3. Let the user type in the text to describe the image
4. Iterate through/display the images

 

When to Use Linked Lists

• Better performance than arrays
• Same as array, but faster and better to work with

 

The biggest difference between linked lists and arrays is when addding and removing
from them. When inserting at the beginning of an array, the array has to resize itself and
shift all of the data. When dealing with a lot of data, this could be a very costly operation.

A linked list can be used to store data that references other similar data. For example, in
a website, images may be in a sort of gallery where the user could click on an arrow that
lets the user go through all of the images. If these images were stored in a linked list,
running through the data would be quick as well as efficient. All the program would have
to do is run through the refernces, and then the image would be set as the current refrence.

There are so many ways to use linked list instead of a dynamic array, but that does not mean
we should just use a linked list. When creating software, we must think about when each
would be better, and how to implement them into our code. In the end, it is up to us to
think and analyze when one would be better over the other.

 

Return to introduction file.