Linked Lists

Question 1

What is a linked list?

Answer 1

A form of sequential collection and it dow not have to be in order. A linked list is made up of independent nodes that may contain any type of data and each node has a reference to the next node in the link.

Question 2

What are the parts of the linked list

Answer 2

Head: this is the first node of the linked-list
nodes: they are the indepentent data store of the value
links: this connects the nodes together
tail: tail is the last node of the links. does not link to anything

Question 3

What is the structure of the node

Answer 3

Data and Reference
The data stores the information and the reference stores the link to the next node.

Question 4

Why use a linked list over an array

Answer 4

1. each elements of a linked list is independent allowing it to delete the node without getting rid of the list
2. We do not need to specify the size of the linked list like we do with an array.
3. arrays cannot insert new arrays
   4 insertion and removals in linked list are very efficient
4. arrays are very good at finding values since it is indexed. linked lists you need to iterate over to find the linked list.
5. random access - accessing an element is very efficient in arrays

Question 5

What types of linked lists are there

Answer 5

• Singly linked list
• circular singly linked list
  -Doubly linked list
• Circular Doubly Linked List

Question 6

Singly Linked list

Answer 6

The most basic of linked lists. The nodes have 2 parts. one for data and one for reference to the next node.

Question 7

What is a Circular Singly/Double Linked List

Answer 7

It is the same thing as a single/double linked list but the last node references the first node creating a circle. This allows us to have the option to go back to the first node

When to use: Games are a good example where you need to move from one person to the next continuously

Question 8

What is a Doubly Linked List

Answer 8

A doubly linked list has two references and data. One reference is to the previous node and the second reference is to the next node. This way you can move back and forth between each other.

ex: Say you are using spotify. You can move to the next song but also reference the previous song.

Question 9

how linked list are stored in Memory

Answer 9

Linked list are stored randomly. When a reference is open it will then select the location.

Question 10

Example of a linked list Node

Answer 10

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

Question 11

example of a simple linked list class

Answer 11

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

Question 12

Method example to iterate over the nodes in the linked list

Answer 12

You can use the special variable __iter__ to define how to iterate.
def __iter__(self):
node = self.head
while node:
yield node
node = node.next

Question 13

method example of inserting new node

Answer 13

def insert(self, value, location):
new_node = Node(value)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
if location == 0:
new_node.next = self.head
self.head = new_node
elif location == -1:
self.tail.next = new_node
self.tail = new_node
else:
temp_node = self.head
index = 0
while index < location - 1 and temp_node.next:
temp_node = temp_node.next
index += 1
if temp_node.next == self.tail:
self.tail.next = new_node
self.tail = new_node
else:
next_node = temp_node.next
temp_node.next = new_node
new_node.next = next_node

Question 14

deletion method example

Answer 14

def deletion(self, location):
if self.head is None:
raise Exception(“The list does not exist”)
if location < -1:
raise Exception(“The location must be greater than or equal to -1”)
if self.head == self.tail:
if location > 0:
raise Exception(“The location is out of bounds”)
else:
self.head = None
self.tail = None
elif location == 0:
self.head = self.head.next
elif location == -1:
if self.head == self.tail:
self.head = None
self.tail = None
else:
node = self.head
while node.next != self.tail:
node = node.next
node.next = None
self.tail = node
else:
index = 0
prev_node = None
node = self.head
while index < location - 1 and node.next != self.tail:
prev_node = node
node = node.next
index += 1
if node.next == self.tail:
if location > index + 2:
raise Exception(‘The location is out of bounds’)
else:
node.next = None
self.tail = node
else:
prev_node.next = node.next