Teaching Kids Programming – Linked List Data Structure

Teaching Kids Programming: Videos on Data Structures and Algorithms

A linked list consists of nodes. Nodes have values proprorties and the point(s) to other nodes. If a node has a next pointer, then we can build a singly direction linked list:

1
2
3
4
5
6
7
8
9
10
11

class Node:
    def __init__(self, val, nextNode = None):
        self.val = val
        self.nextNode = nextNode
 
    # create a new node with value val and 
    # link it to the current node
    def addNext(self, val):
        newNode = Node(val)
        self.nextNode = newNode
        return newNode

class Node:
    def __init__(self, val, nextNode = None):
        self.val = val
        self.nextNode = nextNode

    # create a new node with value val and 
    # link it to the current node
    def addNext(self, val):
        newNode = Node(val)
        self.nextNode = newNode
        return newNode

If a node has another pointer pointing to previous Node, then we can build a doubly linked list. A Linked list is a sparse data structure where nodes in memory can be sparsely located. Unlike array/list, the memory addresses are continuously allocated. If you append a new element into a list/array, in the worst case, the time complexity is O(N) because the computer has to look for a new big space that is enough to hold all elements. Inserting or deleting an element takes O(N) time.

Inserting, deleting, appending to the end or begining to a linked list is O(1) constant. However, sequential access is O(N) for a linked list, but you may speed it up using a hash map which allows you to locate a node in the middle of the linked list in O(1) constant time.

The following Python code creates a linked list, and traverse it (in O(N)) from the begining. And it will print out values from -1 to 9.

1
2
3
4
5
6
7
8

head = Node(-1)
p = head
for i in range(10):
    p = p.addNext(i)
    
while head:
    print(head.val)
    head = head.nextNode

head = Node(-1)
p = head
for i in range(10):
    p = p.addNext(i)
    
while head:
    print(head.val)
    head = head.nextNode

–EOF (The Ultimate Computing & Technology Blog)