Standard approach for implementation of a list is are of

OperationsEdit

Implementation of the list data structure may provide some of the following operations:

Table of Contents Show

OperationsEdit
ImplementationsEdit
5.2.1. The List ADT
5.2.1.1. Defining the ADT
How to create a Linked List in Python
Python Library for Linked List
Priority Queue using Linked List
Linked Lists in Python: An Introduction

a constructor for creating an empty list;
an operation for testing whether or not a list is empty;
an operation for prepending an entity to a list
an operation for appending an entity to a list
an operation for determining the first component (or the "head") of a list
an operation for referring to the list consisting of all the components of a list except for its first (this is called the "tail" of the list.)
an operation for accessing the element at a given index.

ImplementationsEdit

Lists are typically implemented either as linked lists (either singly or doubly linked) or as arrays, usually variable length or dynamic arrays.

The standard way of implementing lists, originating with the programming language Lisp, is to have each element of the list contain both its value and a pointer indicating the location of the next element in the list. This results in either a linked list or a tree, depending on whether the list has nested sublists. Some older Lisp implementations (such as the Lisp implementation of the Symbolics 3600) also supported "compressed lists" (using CDR coding) which had a special internal representation (invisible to the user). Lists can be manipulated using iteration or recursion. The former is often preferred in imperative programming languages, while the latter is the norm in functional languages.

Lists can be implemented as self-balancing binary search trees holding index-value pairs, providing equal-time access to any element (e.g. all residing in the fringe, and internal nodes storing the right-most child's index, used to guide the search), taking the time logarithmic in the list's size, but as long as it doesn't change much will provide the illusion of random access and enable swap, prefix and append operations in logarithmic time as well.[3]

5.2.1. The List ADT

We all have an intuitive understanding of what we mean by a “list”. We want to turn this intuitive understanding into a concrete data structure with implementations for its operations. The most important concept related to lists is that of position. In other words, we perceive that there is a first element in the list, a second element, and so on. So, define a list to be a finite, ordered sequence of data items known as elements. This is close to the mathematical concept of a sequence.

“Ordered” in this definition means that each element has a position in the list. So the term “ordered” in this context does not mean that the list elements are sorted by value. (Of course, we can always choose to sort the elements on the list if we want; it’s just that keeping the elements sorted is not an inherent property of being a list.)

Each list element must have some data type. In the simple list implementations discussed in this chapter, all elements of the list are usually assumed to have the same data type, although there is no conceptual objection to lists whose elements have differing data types if the application requires it. The operations defined as part of the list ADT do not depend on the elemental data type. For example, the list ADT can be used for lists of integers, lists of characters, lists of payroll records, even lists of lists.

A list is said to be empty when it contains no elements. The number of elements currently stored is called the length of the list. The beginning of the list is called the head, the end of the list is called the tail.

We need some notation to show the contents of a list, so we will use the same angle bracket notation that is normally used to represent sequences. To be consistent with standard array indexing, the first position on the list is denoted as 0. Thus, if there are \(n\) elements in the list, they are given positions 0 through \(n-1\) as \(\langle\ a_0,\ a_1,\ ...,\ a_{n-1}\ \rangle\). The subscript indicates an element’s position within the list. Using this notation, the empty list would appear as \(\langle\ \rangle\).

5.2.1.1. Defining the ADT

What basic operations do we want our lists to support? Our common intuition about lists tells us that a list should be able to grow and shrink in size as we insert and remove elements. We should be able to insert and remove elements from anywhere in the list. We should be able to gain access to any element’s value, either to read it or to change it. We must be able to create and clear (or reinitialize) lists. It is also convenient to access the next or previous element from the “current” one.

Now we can define the ADT for a list object in terms of a set of operations on that object. We will use an interface to formally define the list ADT. List defines the member functions that any list implementation inheriting from it must support, along with their parameters and return types.

True to the notion of an ADT, an interface does not specify how operations are implemented. Two complete implementations are presented later in later modules, both of which use the same list ADT to define their operations. But they are considerably different in approaches and in their space/time tradeoffs.

The code below presents our list ADT. Any implementation for a container class such as a list should be able to support different data types for the elements. One way to do this in Java is to store data values of type Object. Languages that support generics (Java) or templates (C++) give more control over the element types.

The comments given with each member function describe what it is intended to do. However, an explanation of the basic design should help make this clearer. Given that we wish to support the concept of a sequence, with access to any position in the list, the need for many of the member functions such as insert and moveToPos is clear. The key design decision embodied in this ADT is support for the concept of a current position. For example, member moveToStart sets the current position to be the first element on the list, while methods next and prev move the current position to the next and previous elements, respectively. The intention is that any implementation for this ADT support the concept of a current position. The current position is where any action such as insertion or deletion will take place. An alternative design is to factor out position as a separate position object, sometimes referred to as an iterator.

// List class ADT. Generalize by using "Object" for the element type. public interface List { // List class ADT // Remove all contents from the list, so it is once again empty public void clear(); // Insert "it" at the current location // The client must ensure that the list's capacity is not exceeded public boolean insert(Object it); // Append "it" at the end of the list // The client must ensure that the list's capacity is not exceeded public boolean append(Object it); // Remove and return the current element public Object remove() throws NoSuchElementException; // Set the current position to the start of the list public void moveToStart(); // Set the current position to the end of the list public void moveToEnd(); // Move the current position one step left, no change if already at beginning public void prev(); // Move the current position one step right, no change if already at end public void next(); // Return the number of elements in the list public int length(); // Return the position of the current element public int currPos(); // Set the current position to "pos" public boolean moveToPos(int pos); // Return true if current position is at end of the list public boolean isAtEnd(); // Return the current element public Object getValue() throws NoSuchElementException; public boolean isEmpty(); }

// List class ADT. Generalize the element type using Java Generics. public interface List { // List class ADT // Remove all contents from the list, so it is once again empty public void clear(); // Insert "it" at the current location // The client must ensure that the list's capacity is not exceeded public boolean insert(E it); // Append "it" at the end of the list // The client must ensure that the list's capacity is not exceeded public boolean append(E it); // Remove and return the current element public E remove() throws NoSuchElementException; // Set the current position to the start of the list public void moveToStart(); // Set the current position to the end of the list public void moveToEnd(); // Move the current position one step left, no change if already at beginning public void prev(); // Move the current position one step right, no change if already at end public void next(); // Return the number of elements in the list public int length(); // Return the position of the current element public int currPos(); // Set the current position to "pos" public boolean moveToPos(int pos); // Return true if current position is at end of the list public boolean isAtEnd(); // Return the current element public E getValue() throws NoSuchElementException; // Tell if the list is empty or not public boolean isEmpty(); }

// List class ADT. class List { // List class ADT public: // Destructor virtual ~ List () =default; // Remove all contents from the list, so it is once again empty virtual void clear() =0; // Insert "it" at the current location // The client must ensure that the list's capacity is not exceeded virtual bool insert(const ListItemType& it) =0; // Append "it" at the end of the list // The client must ensure that the list's capacity is not exceeded virtual bool append(const ListItemType& it) =0; // Remove and return the current element virtual ListItemType remove() =0; // Set the current position to the start of the list virtual void moveToStart() =0; // Set the current position to the end of the list virtual void moveToEnd() =0; // Move the current position one step left, no change if already at beginning virtual void prev() =0; // Move the current position one step right, no change if already at end virtual void next() =0; // Return the number of elements in the list virtual int length() =0; // Return the position of the current element virtual int currPos() =0; // Set the current position to "pos" virtual bool moveToPos(int pos) =0; // Return true if current position is at end of the list virtual bool isAtEnd() =0; // Return the current element virtual ListItemType getValue() =0; virtual bool isEmpty() =0; };

The List member functions allow you to build a list with elements in any desired order, and to access any desired position in the list. You might notice that the clear method is a “convenience” method, since it could be implemented by means of the other member functions in the same asymptotic time.

A list can be iterated through as follows:

for (L.moveToStart(); !L.isAtEnd(); L.next()) { it = L.getValue(); doSomething(it); }

In this example, each element of the list in turn is stored in it, and passed to the doSomething function. The loop terminates when the current position reaches the end of the list.

The list class declaration presented here is just one of many possible interpretations for lists. Our list interface provides most of the operations that one naturally expects to perform on lists and serves to illustrate the issues relevant to implementing the list data structure. As an example of using the list ADT, here is a function to return true if there is an occurrence of a given integer in the list, and false otherwise. The find method needs no knowledge about the specific list implementation, just the list ADT.

// Return true if k is in list L, false otherwise static boolean find(List L, Object k) { for (L.moveToStart(); !L.isAtEnd(); L.next()) if (k == L.getValue()) return true; // Found k return false; // k not found }

// Return true if k is in list L, false otherwise static boolean find(List L, int k) { for (L.moveToStart(); !L.isAtEnd(); L.next()) { if (k == L.getValue()) { return true; // Found k } } return false; // k not found }

// Return true if k is in list L, false otherwise static bool find(List &L, ListItemType k) { for (L.moveToStart(); !L.isAtEnd(); L.next()) if (k == L.getValue()) return true; // Found k return false; // k not found }

In languages that support it, this implementation for find could be rewritten as a generic or template with respect to the element type. While making it more flexible, even generic types still are limited in their ability to handle different data types stored on the list. In particular, for the find function generic types would only work when the description for the object being searched for (k in the function) is of the same type as the objects themselves. They also have to be comparable when using the == operator. A more realistic situation is that we are searching for a record that contains a key field whose value matches k. Similar functions to find and return a composite type based on a key value can be created using the list implementation, but to do so requires some agreement between the list ADT and the find function on the concept of a key, and on how keys may be compared.

There are two standard approaches to implementing lists, the array-based list, and the linked list.

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.

Python Library for Linked List

Linked list is a simple data structure in programming, which obviously is used to store data and retrieve it accordingly. To make it easier to imagine, it is more like a dynamic array in which data elements are linked via pointers (i.e. the present record points to its next record and the next one points to the record that comes after it, this goes on until the end of the structure) rather than being tightly packed.
There are two types of linked list:

Single-Linked List: In this, the nodes point to the node immediately after it
Doubly Linked List: In this, the nodes not only reference the node next to it but also the node before it.

Priority Queue using Linked List

Implement Priority Queue using Linked Lists.

push(): This function is used to insert a new data into the queue.
pop(): This function removes the element with the highest priority from the queue.
peek() / top(): This function is used to get the highest priority element in the queue without removing it from the queue.

Priority Queues can be implemented using common data structures like arrays, linked-lists, heaps and binary trees.

Prerequisites :
Linked Lists, Priority Queues

The list is so created so that the highest priority element is always at the head of the list. The list is arranged in descending order of elements based on their priority. This allow us to remove the highest priority element in O(1) time. To insert an element we must traverse the list and find the proper position to insert the node so that the overall order of the priority queue is maintained. This makes the push() operation takes O(N) time. The pop() and peek() operations are performed in constant time.

Algorithm :
PUSH(HEAD, DATA, PRIORITY)
Step 1: Create new node with DATA and PRIORITY
Step 2: Check if HEAD has lower priority. If true follow Steps 3-4 and end. Else goto Step 5.
Step 3: NEW -> NEXT = HEAD
Step 4: HEAD = NEW
Step 5: Set TEMP to head of the list
Step 6: While TEMP -> NEXT != NULL and TEMP -> NEXT -> PRIORITY > PRIORITY
Step 7: TEMP = TEMP -> NEXT
[END OF LOOP]
Step 8: NEW -> NEXT = TEMP -> NEXT
Step 9: TEMP -> NEXT = NEW
Step 10: End
POP(HEAD)
Step 2: Set the head of the list to the next node in the list. HEAD = HEAD -> NEXT.
Step 3: Free the node at the head of the list
Step 4: End
PEEK(HEAD):
Step 1: Return HEAD -> DATA
Step 2: End

Below is the implementation of the algorithm :

C++

// C++ code to implement Priority Queue 
// using Linked List 
#include <bits/stdc++.h> 

using namespace std;
// Node 

typedef struct node
{ 

int data;

// Lower values indicate

// higher priority

int priority;

struct node* next;
} Node; 
// Function to create a new node 

Node* newNode(int d, int p)
{ 

Node* temp = (Node*)malloc(sizeof(Node));

temp->data = d;

temp->priority = p;

temp->next = NULL;

return temp;
} 
// Return the value at head 

int peek(Node** head)
{ 

return (*head)->data;
} 
// Removes the element with the 
// highest priority form the list 

void pop(Node** head)
{ 

Node* temp = *head;

(*head) = (*head)->next;

free(temp);
} 
// Function to push according to priority 

void push(Node** head, int d, int p)
{ 

Node* start = (*head);

// Create new Node

Node* temp = newNode(d, p);

// Special Case: The head of list has

// lesser priority than new node. So

// insert newnode before head node

// and change head node.

if ((*head)->priority > p)

{

// Insert New Node before head

temp->next = *head;

(*head) = temp;

}

else

{

// Traverse the list and find a

// position to insert new node

while (start->next != NULL &&

start->next->priority < p)

{

start = start->next;

}

// Either at the ends of the list

// or at required position

temp->next = start->next;

start->next = temp;

}
} 
// Function to check is list is empty 

int isEmpty(Node** head)
{ 

return (*head) == NULL;
} 
// Driver code 

int main()
{ 

// Create a Priority Queue

// 7->4->5->6

Node* pq = newNode(4, 1);

push(&pq, 5, 2);

push(&pq, 6, 3);

push(&pq, 7, 0);

while (!isEmpty(&pq))

{

cout << " " << peek(&pq);

pop(&pq);

}

return 0;
} 
// This code is contributed by shivanisinghss2110

// C code to implement Priority Queue 
// using Linked List 
#include <stdio.h> 
#include <stdlib.h> 
// Node 

typedef struct node {

int data;

// Lower values indicate higher priority

int priority;

struct node* next;
} Node; 
// Function to Create A New Node 

Node* newNode(int d, int p)
{ 

Node* temp = (Node*)malloc(sizeof(Node));

temp->data = d;

temp->priority = p;

temp->next = NULL;

return temp;
} 
// Return the value at head 

int peek(Node** head)
{ 

return (*head)->data;
} 
// Removes the element with the 
// highest priority form the list 

void pop(Node** head)
{ 

Node* temp = *head;

(*head) = (*head)->next;

free(temp);
} 
// Function to push according to priority 

void push(Node** head, int d, int p)
{ 

Node* start = (*head);

// Create new Node

Node* temp = newNode(d, p);

// Special Case: The head of list has lesser

// priority than new node. So insert new

// node before head node and change head node.

if ((*head)->priority > p) {

// Insert New Node before head

temp->next = *head;

(*head) = temp;

}

else {

// Traverse the list and find a

// position to insert new node

while (start->next != NULL &&

start->next->priority < p) {

start = start->next;

}

// Either at the ends of the list

// or at required position

temp->next = start->next;

start->next = temp;

}
} 
// Function to check is list is empty 

int isEmpty(Node** head)
{ 

return (*head) == NULL;
} 
// Driver code 

int main()
{ 

// Create a Priority Queue

// 7->4->5->6

Node* pq = newNode(4, 1);

push(&pq, 5, 2);

push(&pq, 6, 3);

push(&pq, 7, 0);

while (!isEmpty(&pq)) {

printf("%d ", peek(&pq));

pop(&pq);

}

return 0;
} 

Java

// Java code to implement Priority Queue 
// using Linked List 

import java.util.* ;

class Solution
{ 

// Node 

static class Node {

int data;

// Lower values indicate higher priority

int priority;

Node next;

} 

static Node node = new Node();

// Function to Create A New Node 

static Node newNode(int d, int p)
{ 

Node temp = new Node();

temp.data = d;

temp.priority = p;

temp.next = null;

return temp;
} 

// Return the value at head 

static int peek(Node head)
{ 

return (head).data;
} 

// Removes the element with the 
// highest priority form the list 

static Node pop(Node head)
{ 

Node temp = head;

(head) = (head).next;

return head;
} 

// Function to push according to priority 

static Node push(Node head, int d, int p)
{ 

Node start = (head);

// Create new Node

Node temp = newNode(d, p);

// Special Case: The head of list has lesser

// priority than new node. So insert new

// node before head node and change head node.

if ((head).priority > p) {

// Insert New Node before head

temp.next = head;

(head) = temp;

}

else {

// Traverse the list and find a

// position to insert new node

while (start.next != null &&

start.next.priority < p) {

start = start.next;

}

// Either at the ends of the list

// or at required position

temp.next = start.next;

start.next = temp;

}

return head;
} 

// Function to check is list is empty 

static int isEmpty(Node head)
{ 

return ((head) == null)?1:0;
} 

// Driver code 

public static void main(String args[])
{ 

// Create a Priority Queue

// 7.4.5.6

Node pq = newNode(4, 1);

pq =push(pq, 5, 2);

pq =push(pq, 6, 3);

pq =push(pq, 7, 0);

while (isEmpty(pq)==0) {

System.out.printf("%d ", peek(pq));

pq=pop(pq);

}

} 
} 
// This code is contributed 
// by Arnab Kundu

Python3

# Python3 code to implement Priority Queue 
# using Singly Linked List 
# Class to create new node which includes
# Node Data, and Node Priority

class PriorityQueueNode:

def __init__(self, value, pr):

self.data = value

self.priority = pr

self.next = None

# Implementation of Priority Queue

class PriorityQueue:

def __init__(self):

self.front = None

# Method to check Priority Queue is Empty

# or not if Empty then it will return True

# Otherwise False

def isEmpty(self):

return True if self.front == None else False

# Method to add items in Priority Queue

# According to their priority value

def push(self, value, priority):

# Condition check for checking Priority

# Queue is empty or not

if self.isEmpty() == True:

# Creating a new node and assigning

# it to class variable

self.front = PriorityQueueNode(value,

priority)

# Returning 1 for successful execution

return 1

else:

# Special condition check to see that

# first node priority value

if self.front.priority > priority:

# Creating a new node

newNode = PriorityQueueNode(value,

priority)

# Updating the new node next value

newNode.next = self.front

# Assigning it to self.front

self.front = newNode

# Returning 1 for successful execution

return 1

else:

# Traversing through Queue until it

# finds the next smaller priority node

temp = self.front

while temp.next:

# If same priority node found then current

# node will come after previous node

if priority <= temp.next.priority:

break

temp = temp.next

newNode = PriorityQueueNode(value,

priority)

newNode.next = temp.next

temp.next = newNode

# Returning 1 for successful execution

return 1

# Method to remove high priority item

# from the Priority Queue

def pop(self):

# Condition check for checking

# Priority Queue is empty or not

if self.isEmpty() == True:

return

else:

# Removing high priority node from

# Priority Queue, and updating front

# with next node

self.front = self.front.next

return 1

# Method to return high priority node

# value Not removing it

def peek(self):

# Condition check for checking Priority

# Queue is empty or not

if self.isEmpty() == True:

return

else:

return self.front.data

# Method to Traverse through Priority

# Queue

def traverse(self):

# Condition check for checking Priority

# Queue is empty or not

if self.isEmpty() == True:

return "Queue is Empty!"

else:

temp = self.front

while temp:

print(temp.data, end = " ")

temp = temp.next
# Driver code

if __name__ == "__main__":

# Creating an instance of Priority

# Queue, and adding values

# 7 -> 4 -> 5 -> 6

pq = PriorityQueue()

pq.push(4, 1)

pq.push(5, 2)

pq.push(6, 3)

pq.push(7, 0)

# Traversing through Priority Queue

pq.traverse()

# Removing highest Priority item

# for priority queue

pq.pop()

# This code is contributed by himanshu kanojiya

// C# code to implement Priority Queue 
// using Linked List 

using System;

class GFG
{ 
// Node 

public class Node
{ 

public int data;

// Lower values indicate

// higher priority

public int priority;

public Node next;
} 

public static Node node = new Node();
// Function to Create A New Node 

public static Node newNode(int d, int p)
{ 

Node temp = new Node();

temp.data = d;

temp.priority = p;

temp.next = null;

return temp;
} 
// Return the value at head 

public static int peek(Node head)
{ 

return (head).data;
} 
// Removes the element with the 
// highest priority form the list 

public static Node pop(Node head)
{ 

Node temp = head;

(head) = (head).next;

return head;
} 
// Function to push according to priority 

public static Node push(Node head,

int d, int p)
{ 

Node start = (head);

// Create new Node

Node temp = newNode(d, p);

// Special Case: The head of list

// has lesser priority than new node.

// So insert new node before head node

// and change head node.

if ((head).priority > p)

{

// Insert New Node before head

temp.next = head;

(head) = temp;

}

else

{

// Traverse the list and find a

// position to insert new node

while (start.next != null &&

start.next.priority < p)

{

start = start.next;

}

// Either at the ends of the list

// or at required position

temp.next = start.next;

start.next = temp;

}

return head;
} 
// Function to check is list is empty 

public static int isEmpty(Node head)
{ 

return ((head) == null) ? 1 : 0;
} 
// Driver code 

public static void Main(string[] args)
{ 

// Create a Priority Queue

// 7.4.5.6

Node pq = newNode(4, 1);

pq = push(pq, 5, 2);

pq = push(pq, 6, 3);

pq = push(pq, 7, 0);

while (isEmpty(pq) == 0)

{

Console.Write("{0:D} ", peek(pq));

pq = pop(pq);

}
} 
} 
// This code is contributed by Shrikant13

Javascript

<script>

// JavaScript code to implement Priority Queue

// using Linked List

// Node

class Node

{

// Lower values indicate

// higher priority

constructor() {

this.data = 0;

this.priority = 0;

this.next = null;

}

}

var node = new Node();

// Function to Create A New Node

function newNode(d, p) {

var temp = new Node();

temp.data = d;

temp.priority = p;

temp.next = null;

return temp;

}

// Return the value at head

function peek(head) {

return head.data;

}

// Removes the element with the

// highest priority form the list

function pop(head) {

var temp = head;

head = head.next;

return head;

}

// Function to push according to priority

function push(head, d, p) {

var start = head;

// Create new Node

var temp = newNode(d, p);

// Special Case: The head of list

// has lesser priority than new node.

// So insert new node before head node

// and change head node.

if (head.priority > p)

{

// Insert New Node before head

temp.next = head;

head = temp;

}

else

{

// Traverse the list and find a

// position to insert new node

while (start.next != null && start.next.priority < p) {

start = start.next;

}

// Either at the ends of the list

// or at required position

temp.next = start.next;

start.next = temp;

}

return head;

}

// Function to check is list is empty

function isEmpty(head) {

return head == null ? 1 : 0;

}

// Driver code

// Create a Priority Queue

// 7.4.5.6

var pq = newNode(4, 1);

pq = push(pq, 5, 2);

pq = push(pq, 6, 3);

pq = push(pq, 7, 0);

while (isEmpty(pq) == 0) {

document.write(peek(pq) + " ");

pq = pop(pq);

}

// This code is contributed by rdtank.

</script>

Output: 7 4 5 6

Time Complexities and Comparison with Binary Heap:

peek() push() pop() ----------------------------------------- Linked List | O(1) O(n) O(1) | Binary Heap | O(1) O(Log n) O(Log n)

Article Tags :

Linked List

Queue

priority-queue

Practice Tags :

Linked List

Queue

priority-queue

Read Full Article

Linked Lists in Python: An Introduction

by Pedro Pregueiro intermediate python

Mark as Completed

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.