Array of linked list Python

Linked Lists in Python: An Introduction

by Pedro Pregueiro intermediate python

Mark as Completed

Table of Contents Show

Linked Lists in Python: An Introduction
Linked List vs Array
Create linked list from a given array
How to create a Linked List in Python
Linked Lists in Python
Simple Linked Lists Data Structure in Python

Tweet Share Email

Table of Contents

Remove ads

Watch Now This tutorial has a related video course created by the Real Python team. Watch it together with the written tutorial to deepen your understanding: Working With Linked Lists in Python

Linked lists are like a lesser-known cousin of lists. They’re not as popular or as cool, and you might not even remember them from your algorithms class. But in the right context, they can really shine.

In this article, you’ll learn:

What linked lists are and when you should use them
How to use collections.deque for all of your linked list needs
How to implement your own linked lists
What the other types of linked lists are and what they can be used for

If you’re looking to brush up on your coding skills for a job interview, or if you want to learn more about Python data structures besides the usual dictionaries and lists, then you’ve come to the right place!

You can follow along with the examples in this tutorial by downloading the source code available at the link below:

Get the Source Code: Click here to get the source code you’ll use to learn about linked lists in this tutorial.

Linked List vs Array

Arrays store elements in contiguous memory locations, resulting in easily calculable addresses for the elements stored and this allows faster access to an element at a specific index. Linked lists are less rigid in their storage structure and elements are usually not stored in contiguous locations, hence they need to be stored with additional tagsgiving a reference to the next element. This difference in the data storage scheme decides which data structure would be more suitable for a given situation.

Data storage scheme of an array

Data storage scheme of a linked list

Major differences are listed below:

Size: Since data can only be stored in contiguous blocks of memory in an array, its size cannot be altered at runtime due to the risk of overwriting other data. However, in a linked list, each node points to the next one such that data can exist at scattered (non-contiguous) addresses; this allows for a dynamic size that can change at runtime.
Memory allocation: For arrays at compile time and at runtime for linked lists. but, a dynamically allocated array also allocates memory at runtime.
Memory efficiency: For the same number of elements, linked lists use more memory as a reference to the next node is also stored along with the data. However, size flexibility in linked lists may make them use less memory overall; this is useful when there is uncertainty about size or there are large variations in the size of data elements; memory equivalent to the upper limit on the size has to be allocated (even if not all of it is being used) while using arrays, whereas linked lists can increase their sizes step-by-step proportionately to the amount of data.
Execution time: Any element in an array can be directly accessed with its index; however in the case of a linked list, all the previous elements must be traversed to reach any element. Also, better cache locality in arrays (due to contiguous memory allocation) can significantly improve performance. As a result, some operations (such as modifying a certain element) are faster in arrays, while some others (such as inserting/deleting an element in the data) are faster in linked lists.

Following are the points in favor of Linked Lists.
(1) The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage, and in practical uses, the upper limit is rarely reached.

(2) Inserting a new element in an array of elements is expensive because room has to be created for the new elements and to create room existing elements have to be shifted.

For example, suppose we maintain a sorted list of IDs in an array id[ ].

id[ ] = [1000, 1010, 1050, 2000, 2040, …..].

And if we want to insert a new ID 1005, then to maintain the sorted order, we have to move all the elements after 1000 (excluding 1000).

Deletion is also expensive with arrays unless some special techniques are used. For example, to delete 1010 in id[], everything after 1010 has to be moved.

So Linked list provides the following two advantages over arrays
1) Dynamic size
2) Ease of insertion/deletion

Linked lists have the following drawbacks:
1) Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do a binary search with linked lists.
2) Extra memory space for a pointer is required with each element of the list.
3) Arrays have better cache locality that can make a pretty big difference in performance.

4) It takes a lot of time in traversing and changing the pointers.

5) It will be confusing when we work with pointers.

References:
http://cslibrary.stanford.edu/103/LinkedListBasics.pdf

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Article Tags :

Arrays

Linked List

Practice Tags :

Linked List

Arrays

Read Full Article

Create linked list from a given array

Given an array arr[] of size N. The task is to create linked list from the given array.
Examples:

Input : arr[]={1, 2, 3, 4, 5} Output : 1->2->3->4->5 Input :arr[]={10, 11, 12, 13, 14} Output : 10->11->12->13->14

Simple Approach: For each element of an array arr[] we create a node in a linked list and insert it at the end.

C++

#include <iostream>

using namespace std;
// Representation of a node

struct Node {

int data;

Node* next;
};
// Function to insert node

void insert(Node** root, int item)
{

Node* temp = new Node;

Node* ptr;

temp->data = item;

temp->next = NULL;

if (*root == NULL)

*root = temp;

else {

ptr = *root;

while (ptr->next != NULL)

ptr = ptr->next;

ptr->next = temp;

}
}

void display(Node* root)
{

while (root != NULL) {

cout << root->data << " ";

root = root->next;

}
}

Node *arrayToList(int arr[], int n)
{

Node *root = NULL;

for (int i = 0; i < n; i++)

insert(&root, arr[i]);

return root;
}
// Driver code

int main()
{

int arr[] = { 1, 2, 3, 4, 5 };

int n = sizeof(arr) / sizeof(arr[0]);

Node* root = arrayToList(arr, n);

display(root);

return 0;
}

Java

// Java implementation of the approach

import java.util.*;

class GFG
{ 

// Representation of a node

static class Node
{

int data;

Node next;
};
// Function to insert node

static Node insert(Node root, int item)
{

Node temp = new Node();

Node ptr;

temp.data = item;

temp.next = null;

if (root == null)

root = temp;

else

{

ptr = root;

while (ptr.next != null)

ptr = ptr.next;

ptr.next = temp;

}

return root;
}

static void display(Node root)
{

while (root != null)

{

System.out.print( root.data + " ");

root = root.next;

}
}

static Node arrayToList(int arr[], int n)
{

Node root = null;

for (int i = 0; i < n; i++)

root = insert(root, arr[i]);

return root;
}
// Driver code

public static void main(String args[])
{

int arr[] = { 1, 2, 3, 4, 5 };

int n = arr.length;

Node root = arrayToList(arr, n);

display(root);
}
}
// This code is contributed by Arnab Kundu

Python3

# Python3 implementation of the approach 

import math
# Representation of a node

class Node:

def __init__(self, data):

self.data = data

self.next = None
# Function to insert node

def insert(root, item):

temp = Node(item)

if (root == None):

root = temp

else :

ptr = root

while (ptr.next != None):

ptr = ptr.next

ptr.next = temp

return root

def display(root):

while (root != None) :

print(root.data, end = " ")

root = root.next

def arrayToList(arr, n):

root = None

for i in range(0, n, 1):

root = insert(root, arr[i])

return root
# Driver code

if __name__=='__main__':

arr = [1, 2, 3, 4, 5]

n = len(arr)

root = arrayToList(arr, n)

display(root)

# This code is contributed by Srathore

// C# implementation of the above approach 

using System;

class GFG
{ 

// Representation of a node

public class Node
{

public int data;

public Node next;
};
// Function to insert node

static Node insert(Node root, int item)
{

Node temp = new Node();

Node ptr;

temp.data = item;

temp.next = null;

if (root == null)

root = temp;

else

{

ptr = root;

while (ptr.next != null)

ptr = ptr.next;

ptr.next = temp;

}

return root;
}

static void display(Node root)
{

while (root != null)

{

Console.Write(root.data + " ");

root = root.next;

}
}

static Node arrayToList(int []arr, int n)
{

Node root = null;

for (int i = 0; i < n; i++)

root = insert(root, arr[i]);

return root;
}
// Driver code

public static void Main(String []args)
{

int []arr = { 1, 2, 3, 4, 5 };

int n = arr.Length;

Node root = arrayToList(arr, n);

display(root);
}
}
// This code is contributed by PrinciRaj1992

Javascript

<script>
// Javascript implementation of the approach
// Representation of a node
class Node {

constructor() {

var data;

var next;

}

}

// Function to insert node

function insert( root, item)
{

var temp = new Node();

var ptr;

temp.data = item;

temp.next = null;

if (root == null)

root = temp;

else

{

ptr = root;

while (ptr.next != null)

ptr = ptr.next;

ptr.next = temp;

}

return root;
}

function display( root)
{

while (root != null)

{

document.write( root.data + " ");

root = root.next;

}
}

function arrayToList( arr, n)
{

var root = null;

for (let i = 0; i < n; i++)

root = insert(root, arr[i]);

return root;
}

// Driver Code

let arr = [ 1, 2, 3, 4, 5 ];

let n = arr.length;

var root = arrayToList(arr, n);

display(root);
// This code is contributed by jana_sayantan.
</script>

Output: 1 2 3 4 5

Time Complexity : O(n*n)
Efficient Approach: We traverse array from end and insert every element at the beginning of the list.

C++

#include <iostream>

using namespace std;
// Representation of a node

struct Node {

int data;

Node* next;
};
// Function to insert node

void insert(Node** root, int item)
{

Node* temp = new Node;

temp->data = item;

temp->next = *root;

*root = temp;
}

void display(Node* root)
{

while (root != NULL) {

cout << root->data << " ";

root = root->next;

}
}

Node *arrayToList(int arr[], int n)
{

Node *root = NULL;

for (int i = n-1; i >= 0 ; i--)

insert(&root, arr[i]);

return root;
}
// Driver code

int main()
{

int arr[] = { 1, 2, 3, 4, 5 };

int n = sizeof(arr) / sizeof(arr[0]);

Node* root = arrayToList(arr, n);

display(root);

return 0;
}

Java

// Java program to print level order traversal
// in spiral form using one queue and one stack.

import java.util.*;

class GFG
{ 
// Representation of a node

static class Node
{

int data;

Node next;
};

static Node root;
// Function to insert node

static Node insert(Node root, int item)
{

Node temp = new Node();

temp.data = item;

temp.next = root;

root = temp;

return root;
}

static void display(Node root)
{

while (root != null)

{

System.out.print(root.data + " ");

root = root.next;

}
}

static Node arrayToList(int arr[], int n)
{

root = null;

for (int i = n - 1; i >= 0 ; i--)

root = insert(root, arr[i]);

return root;
}
// Driver code

public static void main(String[] args)
{

int arr[] = { 1, 2, 3, 4, 5 };

int n = arr.length;

Node root = arrayToList(arr, n);

display(root);
}
}
// This code is contributed by Princi Singh

Python3

# Python3 program to print level order traversal 
# in spiral form using one queue and one stack. 
# Representation of a Node 

class Node:

def __init__(self, data):

self.data = data

self.next = next
# Function to insert Node 

def insert(root, item):

temp = Node(0)

temp.data = item

temp.next = root

root = temp

return root

def display(root):

while (root != None):

print(root.data, end=" ")

root = root.next

def arrayToList(arr, n):

root = None

for i in range(n - 1, -1, -1):

root = insert(root, arr[i])

return root
# Driver code 

if __name__ == '__main__':

arr = [1, 2, 3, 4, 5];

n = len(arr)

root = arrayToList(arr, n);

display(root)
# This code is contributed by 29AjayKumar

// C# program to print level order traversal
// in spiral form using one queue and one stack.

using System;

class GFG
{ 
// Representation of a node

public class Node
{

public int data;

public Node next;
};

static Node root;
// Function to insert node

static Node insert(Node root, int item)
{

Node temp = new Node();

temp.data = item;

temp.next = root;

root = temp;

return root;
}

static void display(Node root)
{

while (root != null)

{

Console.Write(root.data + " ");

root = root.next;

}
}

static Node arrayToList(int []arr, int n)
{

root = null;

for (int i = n - 1; i >= 0 ; i--)

root = insert(root, arr[i]);

return root;
}
// Driver code

public static void Main(String[] args)
{

int []arr = { 1, 2, 3, 4, 5 };

int n = arr.Length;

Node root = arrayToList(arr, n);

display(root);
}
}
// This code is contributed by Rajput-Ji

Javascript

<script>

// JavaScript program to print level order traversal

// in spiral form using one queue and one stack.

// Representation of a node

class Node {

constructor() {

this.data = 0;

this.next = null;

}

}

var root;

// Function to insert node

function insert(root, item) {

var temp = new Node();

temp.data = item;

temp.next = root;

root = temp;

return root;

}

function display(root) {

while (root != null) {

document.write(root.data + " ");

root = root.next;

}

}

function arrayToList(arr, n) {

root = null;

for (var i = n - 1; i >= 0; i--) root = insert(root, arr[i]);

return root;

}

// Driver code

var arr = [1, 2, 3, 4, 5];

var n = arr.length;

var root = arrayToList(arr, n);

display(root);

</script>

Output: 1 2 3 4 5

Time Complexity : O(n)
Alternate Efficient Solution is maintain tail pointer, traverse array elements from left to right, insert at tail and update tail after insertion.

Article Tags :

Arrays

Linked List

Practice Tags :

Linked List

Arrays

Read Full Article

How to create a Linked List in Python

A linked list is a data structure made of a chain of node objects. Each node contains a value and a pointer to the next node in the chain.

Linked lists are preferred over arrays due to their dynamic size and ease of insertion and deletion properties.

The head pointer points to the first node, and the last element of the list points to null. When the list is empty, the head pointer points to null.

Linked Lists in Python

By Dan Bader — Get free updates of new posts here.

Learn how to implement a linked list data structure in Python, using only built-in data types and functionality from the standard library.

Every Python programmer should know about linked lists:

They are among the simplest and most common data structures used in programming.

So, if you ever found yourself wondering, “Does Python have a built-in or ‘native’ linked list data structure?” or, “How do I write a linked list in Python?” then this tutorial will help you.

Python doesn’t ship with a built-in linked list data type in the “classical” sense. Python’s list type is implemented as a dynamic array—which means it doesn’t suit the typical scenarios where you’d want to use a “proper” linked list data structure for performance reasons.

Please note that this tutorial only considers linked list implementations that work on a “plain vanilla” Python install. I’m leaving out third-party packages intentionally. They don’t apply during coding interviews and it’s difficult to keep an up-to-date list that considers all packages available on Python packaging repositories.

Before we get into the weeds and look at linked list implementations in Python, let’s do a quick recap of what a linked list data structure is—and how it compares to an array.

Simple Linked Lists Data Structure in Python

Photo by Patrick Tomasso on Unsplash

Hi everyone, in this article, we will talk about simple linked lists, one of the most commonly used data structures. Firstly, we will see what a linked list is, how the data is stored, the advantages and drawbacks of using it. After that, we will see the main operations in a linked list and we will implement them in Python. So, let’s start.