Linked Lists

Question 1

What are linked lists?

Answer 1

• linear collection of data elements made up of nodes
• a node contains a link to the next node in the list and some unit of data(str, int, list,set,etc) thats called the cargo
• last node in linked list points to None because it doesn’t provide a link to other nodes
• beginning of LL is called ‘head’
• end is ‘tail’

Question 2

What are the advantages of using a linked list over a regular list?

Answer 2

• dynamically shrink or grow at run-time
• faster insertion and deletion
• efficient memory management
• implementation of data structures

Question 3

Disadvantages

Answer 3

• more memory used for each element(own cargo and pointer to next node)
• random access(cant directly index)
• no easy way for reverse traversal

Question 4

The Node Class

Answer 4

class Node:
    '''An object that represents and element in a linked list'''

    def \_\_init\_\_(self, cargo=None, next=None):
        '''
        (self,object,Node) -> NoneType
        '''
        self.cargo = cargo
        self.next  = next

    def \_\_str\_\_(self):
        return str(self.cargo)

• to link nodes, have to make first node refer to second and etc
  node1. next = node2
  node2. next = node3
• refernce of node 3 is None
• the head (node1) serves as a reference to entire collection
• to pass linked list as a parameter, only hv to pass the reference to head node

Question 5

Traversing a Linked List

Answer 5

• takes a single node as an argument(usually head) and prints each node until it gets to end(tail) of LL

class Node:
    def \_\_init\_\_(self, cargo=None, next=None):
        self.cargo = cargo
        self.next  = next

    def \_\_str\_\_(self):
        return str(self.cargo)

#function to print linked nodes
def print_list(n):
    while n:
        print(n, end=" ")
        n = n.next

node1 = Node(1)
node2 = Node(2)
node3 = Node(3)

node1. next = node2
node2. next = node3

print_list(node1)
–> 1 2 3
print_list(node2)
–> 2 3

Question 6

LinkedList Class

Answer 6

A LinkedList class typically has two attributes: head, which keeps track of the first element of the linked lists and 
length, which stores length of the linked list, and  includes methods such as add_first, add_last and remove_item