DSA 33: Nodes & Linked Lists [Part 1]

1. Node

Has two primary instance attributes:

• .data: The data for the node to store (string used below)
• .next_node: link to the next node

Unlikes arrays:

• nodes (and node data) are not stored contiguously in memory,
• rather each node points to the .next_node.

1.1. Node Data Structure: Advantages

• Not being contiguous in memory is nodes, thus
• Will not have the same issues as arrays to find slots of memory

1.2 Node Data Structure: Disadvantages

• The drawback is nodes take up more memory.

class Node():
    def __init__(self, data):
        self.data = data
        self.next_node = None
        
node0 = Node("I've")
node1 = Node("paid")
node2 = Node("my")
node3 = Node("dues")

node0.next_node = node1
node1.next_node = node2
node2.next_node = node3
node3.next_node = None

print(node0.data, node0.next_node.data,sep="\t")
print(node1.data, node1.next_node.data,sep="\t")
print(node2.data, node2.next_node.data,sep="\t")
print(node3.data)

I've    paid
paid    my
my  dues
dues

2. LinkedList

The only information required at (this point) to instantiate a LinkedList is to supply a single instance attribute argument firstnode:

• By providing node0 node instance created earlier,
  
• Able to navigate to all subsequence nodes (node instances):
  • with .next_node attribute of each node
• Obtain each node’s data from .data instance attributes.

class LinkedList:
    def __init__(self, first_node):
        self.first_node = first_node
        
ll = LinkedList(node0)

print(ll.first_node.data)
print(ll.first_node.next_node.data)
print(ll.first_node.next_node.next_node.data)
print(ll.first_node.next_node.next_node.next_node.data)

I've
paid
my
dues