Data structures in Python, Series 1: Linked Lists

Why use linked lists?

Linked list is often compared to arrays. Whereas an array is a fixed size of sequence, a linked list can have its elements to be dynamically allocated. What are the pros and cons of these characteristics? Here are some major ones:

Advantages

A linked list saves memory. It only allocates the memory required for values to be stored. In arrays, you have to set an array size before filling it with values, which can potentially waste memory.

Linked list nodes can live anywhere in the memory. Whereas an array requires a sequence of memory to be initiated, as long as the references are updated, each linked list node can be flexibly moved to a different address.

Disadvantages

Linear look up time. When looking for a value in a linked list, you have to start from the beginning of chain, and check one element at a time for a value you’re looking for. If the linked list is n elements long, this can take up to n time. On the contrary many languages allow constant lookups in arrays.

Traversing values

Values can be traversed like this. You start from the head node, check its value, and move on to the next node. Once you hit the end of the linked list, the node should not have any value (None).

Side Note: It’s weird to talk about linked lists in python because this data structure is too low level to be useful in python programs. So don’t blame me if you don’t see the point of coding all this in Python. After all, there’s not much point in using linked list in Python besides its educational value and usefulness in coding interviews. In other languages like C and C++, where linked lists are actually crucial to any programs you’re implementing.

thanks to https://medium.com/@kojinoshiba/data-structures-in-python-series-1-linked-lists-d9f848537b4d

# -*- coding: utf-8 -*-
"""
Here's how you implement a linked list in python
so first we will define a node structure in the class Node
then right now we just make two 
@author: zeus
"""
def traverse(N1):
    temp = N1
    while (temp != None):
        print(temp.val)
        temp = temp.next
class Node:
    def __init__(self,value):
        self.val = value
        self.next = None
N1 = Node(12)
N2 = Node(99)
N3 = Node(37)
N1.next = N2
N2.next = N3
traverse(N1)