Linked Lists

Question 1

Linked List node class constructor code

Answer 1

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

Question 2

Linked List constructor code

Answer 2

class LinkedList:
    def \_\_init\_\_(self, value):
        new_node = Node(value)
        self.head = new_node
        self.tail = new_node
        self.length = 1

Question 3

Linked List print list code

Answer 3

def print_list(self):
        temp = self.head
        while temp is not None:
            print(temp.value)
            temp = temp.next

Question 4

Linked List append code

Answer 4

def append(self, value):
        new_node = Node(value)
        if self.length == 0:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        self.length += 1
        return True

Question 5

Linked List pop code

Answer 5

def pop(self):
        if self.length == 0:
            return None
        temp = self.head
        pre = self.head
        while(temp.next):
            pre = temp
            temp = temp.next
        self.tail = pre
        self.tail.next = None
        self.length -= 1
        if self.length == 0:
            self.head = None
            self.tail = None
        return temp

Question 6

Linked List prepend code

Answer 6

def prepend(self, value):
        new_node = Node(value)
        if self.length == 0:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head = new_node
        self.length += 1
        return True

Question 7

Linked List pop_first code

Answer 7

def pop_first(self):
        if self.length == 0:
            return None
        temp = self.head
        self.head = self.head.next
        temp.next = None
        self.length -= 1
        if self.length == 0:
            self.tail = None
        return temp

Question 8

Linked List get code

Answer 8

def get(self, index):
        if index < 0 or index >= self.length:
            return None
        temp = self.head
        for _ in range(index):
            temp = temp.next
        return temp

Question 9

Linked List set value code

Answer 9

def set_value(self, index, value):
        temp = self.get(index)
        if temp:
            temp.value = value
            return True
        return False

Question 10

Linked List insert code

Answer 10

def insert(self, index, value):
        if index < 0 or index > self.length:
            return False
        if index == 0:
            return self.prepend(value)
        if index == self.length:
            return self.append(value)
        new_node = Node(value)
        temp = self.get(index - 1)
        new_node.next = temp.next
        temp.next = new_node
        self.length += 1   
        return True

Question 11

Linked List remove code

Answer 11

def remove(self, index):
        if index < 0 or index >= self.length:
            return None
        if index == 0:
            return self.pop_first()
        if index == self.length - 1:
            return self.pop()
        pre = self.get(index - 1)
        temp = pre.next
        pre.next = temp.next
        temp.next = None
        self.length -= 1
        return temp

Question 12

Linked List reverse code

Answer 12

def reverse(self):
        temp = self.head
        self.head = self.tail
        self.tail = temp
        after = temp.next
        before = None
        for _ in range(self.length):
            after = temp.next
            temp.next = before
            before = temp
            temp = after

Question 13

Removing an item from the tail end of a Linked List is which Big O?

Answer 13

O(n)

Because you have to start at the beginning of the Linked List an iterate through to the end

Question 14

Removing an item from the beginning of a Linked List is which Big O?

Answer 14

O(1)

This is a place where Linked Lists are better than Lists. Lists are O(n) when removing the first item because of the reindexing that is required.

Question 15

Finding an item by index in a Linked List is which Big O?

Answer 15

O(n)

You have to iterate through the Linked List until you get to the index you are looking for.

Question 16

Linked List Big O of Append?

Answer 16

O(1)

Question 17

Linked List Big O of Pop?

Answer 17

O(n)

Question 18

Linked List Big O of Prepend?

Answer 18

O(1)

Question 19

Linked List Big O of Pop (first)?

Answer 19

O(1)

Question 20

Linked List Big O of Insert

Answer 20

O(n)

Question 21

Linked List Big O of Remove

Answer 21

O(n)

Question 22

Linked List Big O of Lookup by Index

Answer 22

O(n)

Question 23

Linked List Big O of Lookup by Value

Answer 23

O(n)

Question 24

Two attributes of a Linked List Node class?

Answer 24

self. value = value

self. next = next