visual representation of linked list

• Trending Now
• Foundational Courses
• Data Science
• Practice Problem
• Machine Learning
• System Design
• DevOps Tutorial

Linked List Data Structure

• Understanding the basics of Linked List
• Introduction to Linked List - Data Structure and Algorithm Tutorials
• Applications, Advantages and Disadvantages of Linked List
• Linked List vs Array

Types of Linked List

• Singly Linked List Tutorial
• Doubly Linked List Tutorial
• Introduction to Circular Linked List

Basic Operations on Linked List

• Insertion in Linked List
• Search an element in a Linked List (Iterative and Recursive)
• Find Length of a Linked List (Iterative and Recursive)
• Reverse a Linked List
• Deletion in Linked List
• Delete a Linked List node at a given position
• Write a function to delete a Linked List
• Write a function to get Nth node in a Linked List
• Program for Nth node from the end of a Linked List
• Top 50 Problems on Linked List Data Structure asked in SDE Interviews

A linked list is a fundamental data structure in computer science. It consists of nodes where each node contains data and a reference (link) to the next node in the sequence. This allows for dynamic memory allocation and efficient insertion and deletion operations compared to arrays.

Table of Content

What is a Linked List?

Linked lists vs arrays.

• Operations of Linked Lists

Linked List Applications

• Basics of Linked List
• Easy Problem on Linked List
• Medium Problem on Linked List
• Hard Problem on Linked List

A linked list is a linear data structure that consists of a series of nodes connected by pointers. Each node contains data and a reference to the next node in the list. Unlike arrays, linked lists allow for efficient insertion or removal of elements from any position in the list, as the nodes are not stored contiguously in memory.

Here’s the comparison of Linked List vs Arrays

Linked List:

• Data Structure: Non-contiguous
• Memory Allocation: Dynamic
• Insertion/Deletion: Efficient
• Access: Sequential
• Data Structure: Contiguous
• Memory Allocation: Static
• Insertion/Deletion: Inefficient
• Access: Random
• Singly Linked List
• Doubly Linked List
• Circular Linked List
• Circular Doubly Linked List
• Header Linked List

Operations of Linked Lists:

• Linked List Insertion
• Reverse a linked list
• Linked List Deletion (Deleting a given key)
• Linked List Deletion (Deleting a key at given position)
• Nth node from the end of a Linked List
• Implementing stacks and queues using linked lists.
• Using linked lists to handle collisions in hash tables.
• Representing graphs using linked lists.
• Allocating and deallocating memory dynamically.

Basics of Linked List:

• What is Linked List
• Introduction to Linked List – Data Structure and Algorithm Tutorials

Easy Problem on Linked List:

• Print the middle of a given linked list
• Write a function that counts the number of times a given int occurs in a Linked List
• Check if a linked list is Circular Linked List
• Count nodes in Circular linked list
• Convert singly linked list into circular linked list
• Exchange first and last nodes in Circular Linked List
• Reverse a Doubly Linked List
• Program to find size of Doubly Linked List
• An interesting method to print reverse of a linked list
• Can we reverse a linked list in less than O(n)?
• Circular Linked List Traversal
• Delete a node in a Doubly Linked List

Medium Problem on Linked List:

• Detect loop in a linked list
• Find length of loop in linked list
• Remove duplicates from a sorted linked list
• Intersection of two Sorted Linked Lists
• QuickSort on Singly Linked List
• Split a Circular Linked List into two halves
• Deletion from a Circular Linked List
• Merge Sort for Doubly Linked List
• Find pairs with given sum in doubly linked list
• Insert value in sorted way in a sorted doubly linked list
• Remove duplicates from an unsorted doubly linked list
• Rotate Doubly linked list by N nodes
• Given only a pointer to a node to be deleted in a singly linked list, how do you delete it?
• Modify contents of Linked List

Hard Problem on Linked List:

• Intersection point of two Linked Lists.
• Circular Queue | Set 2 (Circular Linked List Implementation)
• Josephus Circle using circular linked list
• The Great Tree-List Recursion Problem.
• Copy a linked list with next and arbit pointer
• Convert a given Binary Tree to Doubly Linked List | Set
• Priority Queue using doubly linked list
• Reverse a doubly linked list in groups of given size
• Reverse a stack without using extra space in O(n)
• Linked List representation of Disjoint Set Data Structures
• Sublist Search (Search a linked list in another list)
• Construct a linked list from 2D matrix

Quick Links :

• ‘Practice Problems’ on Linked List
• ‘Videos’ on Linked List
• ‘Quizzes’ on Linked List

Recomended:

• Learn Data Structure and Algorithms | DSA Tutorial

Please Login to comment...

Related articles, improve your coding skills with practice.

What kind of Experience do you want to share?

Linked List Visualizer

An online web app to visualize different functionalities and operations of a Linked List.

Source Code

Visu Algo .net/en

Visualising data structures and algorithms through animation.

VisuAlgo project is funded by Optiver for 2023-2024. We now open VisuAlgo account registration to every Computer Science students/teachers worldwide and have started various upgrading (sub)-projects.

Do You Know? Next Random Tip

VisuAlgo is a trilingual site. Try visiting the other versions of VisuAlgo other than the default English version , e.g.,  Chinese  or  Indonesian . Users can see the translation statistics for these three pages. We aim to make all three has near 100% translation rate. Unfortunately the translation progress with other languages are too far behind and they are thus redirected to English.

In VisuAlgo, you can use your own input for any algorithm instead of using only the provided sample inputs. This is one of the key feature of VisuAlgo. Try the graph drawing feature in these 9 graph-related visualizations: Graph DS , DFS/BFS , MST , SSSP , Max Flow , Matching , MVC , Steiner Tree , and TSP . You can also click tag 'graph' in any of these 9 graph-related visualization boxes or type in 'graph' in the search box.

Here are some of the newer visualization features: ability to show two visualization scales (1.0x and 0.5x), the zoom-out scale is used to show operations of a slightly bigger test cases,  /list (the linked list are no longer automatically re-layout for most cases to strengthen the O(1) impression of almost all Linked List operations).

Breaking news [Fri, 09 Jun 23]: VisuAlgo project is funded by Optiver starting today. We now open VisuAlgo account registration to every Computer Science students/teachers worldwide. Go to the login page and follow the on-screen instructions to create a new VisuAlgo account (no longer restricted to 'nus.edu'-related emails).

To compare 2 related algorithms, e.g., Kruskal's vs Prim's on the same graph, or 2 related operations of the same data structure, e.g., visualizing Binary (Max) Heap as a Binary Tree or as a Compact Array, open 2 VisuAlgo pages in 2 windows and juxtapose them. Click here to see the screenshot. This juxtaposition technique can be used anytime you want to compare two similar data structures or algorithms.

You can visualize the recursion tree (or DAG, if there are overlapping subproblems and Dynamic Programming (DP) is applicable) of ANY valid recursive function that can be written in JavaScript. Click here to see the screenshot. Obviously do not try visualizing recursion with a gigantic recursion tree as doing so will crash your own web browser/computer.

VisuAlgo loads fast for first time visitors (we use Cloudflare global CDN), but it loads 'almost instantly' for returning visitors as we also cache lots of static content of VisuAlgo :). So, do not use incognito or private browsing mode to keep the cache. Moreover, for NUS students with VisuAlgo accounts, we will load VisuAlgo according to your preferences/class setup after you login .

Each visualization page has an 'e-Lecture Mode' that is accessible from that page's top right corner. This mode is automatically shown to first time (or non logged-in) visitors to showcase the data structure or algorithm being visualized. The quality of e-Lecture mode for many visualization pages have reached the lecture standard of algorithm classes in National University of Singapore :).

Please check the newest features of VisuAlgo: 1). User accounts system for NUS students and verified CS lecturers worldwide (and also read the latest Privacy Policy popup at the bottom right corner), 2). More mobile-friendly setup, 3). More polished e-Lecture notes to reach "NUS standard", and 4). Trilingual capability (/en, /zh, or /id).

VisuAlgo has two main components: The 24 visualization pages and their associated Online Quiz component (more questions are currently being added into the question bank). We do not script any of the questions in Online Quiz :O and all answers will be graded almost instantly :). You can this online quiz system by clicking the 'Training' button on the visualization module.

Array ✍

Sorting ✍ training, bitmask ✍ training, linked list ✍ training, binary heap ✍ training, hash table ✍ training, binary search tree ✍ training, graph structures ✍ training, union-find ds ✍ training, fenwick tree ✍ training, segment tree ✍ training, recursion tree/dag ✍ training, graph traversal ✍ training, min spanning tree ✍ training, ss shortest paths ✍ training, cycle finding ✍ training, suffix tree ✍ training, suffix array ✍ training, geometry (polygon) ✍ training, convex hull ✍ training, network flow ✍ training, graph matching ✍ training, min vertex cover ✍ training, steiner tree ✍ training, traveling salesper... ✍ training, np-complete reduct... ✍.

Reload screen or rotate device for a pathway suiting your device orientation

Initially conceived in 2011 by Associate Professor Steven Halim, VisuAlgo aimed to facilitate a deeper understanding of data structures and algorithms for his students by providing a self-paced, interactive learning platform.

Featuring numerous advanced algorithms discussed in Dr. Steven Halim's book, 'Competitive Programming' — co-authored with Dr. Felix Halim and Dr. Suhendry Effendy — VisuAlgo remains the exclusive platform for visualizing and animating several of these complex algorithms even after a decade.

While primarily designed for National University of Singapore (NUS) students enrolled in various data structure and algorithm courses (e.g., CS1010/equivalent, CS2040/equivalent (including IT5003), CS3230, CS3233, and CS4234), VisuAlgo also serves as a valuable resource for inquisitive minds worldwide, promoting online learning.

Initially, VisuAlgo was not designed for small touch screens like smartphones, as intricate algorithm visualizations required substantial pixel space and click-and-drag interactions. For an optimal user experience, a minimum screen resolution of 1366x768 is recommended. However, since April 2022, a mobile (lite) version of VisuAlgo has been made available, making it possible to use a subset of VisuAlgo features on smartphone screens.

VisuAlgo remains a work in progress, with the ongoing development of more complex visualizations. At present, the platform features 24 visualization modules.

Equipped with a built-in question generator and answer verifier, VisuAlgo's "online quiz system" enables students to test their knowledge of basic data structures and algorithms. Questions are randomly generated based on specific rules, and students' answers are automatically graded upon submission to our grading server. As more CS instructors adopt this online quiz system worldwide, it could effectively eliminate manual basic data structure and algorithm questions from standard Computer Science exams in many universities. By assigning a small (but non-zero) weight to passing the online quiz, CS instructors can significantly enhance their students' mastery of these basic concepts, as they have access to an almost unlimited number of practice questions that can be instantly verified before taking the online quiz. Each VisuAlgo visualization module now includes its own online quiz component.

VisuAlgo has been translated into three primary languages: English, Chinese, and Indonesian. Additionally, we have authored public notes about VisuAlgo in various languages, including Indonesian, Korean, Vietnamese, and Thai:

Project Leader & Advisor (Jul 2011-present) Associate Professor Steven Halim , School of Computing (SoC), National University of Singapore (NUS) Dr Felix Halim , Senior Software Engineer, Google (Mountain View)

Undergraduate Student Researchers 1 CDTL TEG 1: Jul 2011-Apr 2012 : Koh Zi Chun, Victor Loh Bo Huai

Final Year Project/UROP students 1 Jul 2012-Dec 2013 : Phan Thi Quynh Trang, Peter Phandi, Albert Millardo Tjindradinata, Nguyen Hoang Duy Jun 2013-Apr 2014 Rose Marie Tan Zhao Yun , Ivan Reinaldo

Undergraduate Student Researchers 2 CDTL TEG 2: May 2014-Jul 2014 : Jonathan Irvin Gunawan, Nathan Azaria, Ian Leow Tze Wei, Nguyen Viet Dung, Nguyen Khac Tung, Steven Kester Yuwono, Cao Shengze, Mohan Jishnu

Final Year Project/UROP students 2 Jun 2014-Apr 2015 : Erin Teo Yi Ling, Wang Zi Jun 2016-Dec 2017 : Truong Ngoc Khanh, John Kevin Tjahjadi, Gabriella Michelle, Muhammad Rais Fathin Mudzakir Aug 2021-Apr 2023 : Liu Guangyuan, Manas Vegi, Sha Long, Vuong Hoang Long, Ting Xiao, Lim Dewen Aloysius

Undergraduate Student Researchers 3 Optiver: Aug 2023-Oct 2023 : Bui Hong Duc, Oleh Naver, Tay Ngan Lin

Final Year Project/UROP students 3 Aug 2023-Apr 2024 : Xiong Jingya, Radian Krisno, Ng Wee Han

List of translators who have contributed ≥ 100 translations can be found at statistics page.

Acknowledgements NUS CDTL gave Teaching Enhancement Grant to kickstart this project. For Academic Year 2023/24, a generous donation from Optiver will be used to further develop VisuAlgo.

Terms of use

VisuAlgo is generously offered at no cost to the global Computer Science community. If you appreciate VisuAlgo, we kindly request that you spread the word about its existence to fellow Computer Science students and instructors . You can share VisuAlgo through social media platforms (e.g., Facebook, YouTube, Instagram, TikTok, Twitter, etc), course webpages, blog reviews, emails, and more.

Data Structures and Algorithms (DSA) students and instructors are welcome to use this website directly for their classes. If you capture screenshots or videos from this site, feel free to use them elsewhere, provided that you cite the URL of this website ( https://visualgo.net ) and/or the list of publications below as references. However, please refrain from downloading VisuAlgo's client-side files and hosting them on your website, as this constitutes plagiarism. At this time, we do not permit others to fork this project or create VisuAlgo variants. Personal use of an offline copy of the client-side VisuAlgo is acceptable.

Please note that VisuAlgo's online quiz component has a substantial server-side element, and it is not easy to save server-side scripts and databases locally. Currently, the general public can access the online quiz system only through the 'training mode.' The 'test mode' offers a more controlled environment for using randomly generated questions and automatic verification in real examinations at NUS.

List of Publications

This work has been presented at the CLI Workshop at the ICPC World Finals 2012 (Poland, Warsaw) and at the IOI Conference at IOI 2012 (Sirmione-Montichiari, Italy). You can click this link to read our 2012 paper about this system (it was not yet called VisuAlgo back in 2012) and this link for the short update in 2015 (to link VisuAlgo name with the previous project).

Bug Reports or Request for New Features

VisuAlgo is not a finished project. Associate Professor Steven Halim is still actively improving VisuAlgo. If you are using VisuAlgo and spot a bug in any of our visualization page/online quiz tool or if you want to request for new features, please contact Associate Professor Steven Halim. His contact is the concatenation of his name and add gmail dot com.

Privacy Policy

Version 1.2 (Updated Fri, 18 Aug 2023).

Since Fri, 18 Aug 2023, we no longer use Google Analytics. Thus, all cookies that we use now are solely for the operations of this website. The annoying cookie-consent popup is now turned off even for first-time visitors.

Since Fri, 07 Jun 2023, thanks to a generous donation by Optiver, anyone in the world can self-create a VisuAlgo account to store a few customization settings (e.g., layout mode, default language, playback speed, etc).

Additionally, for NUS students, by using a VisuAlgo account (a tuple of NUS official email address, student name as in the class roster, and a password that is encrypted on the server side — no other personal data is stored), you are giving a consent for your course lecturer to keep track of your e-lecture slides reading and online quiz training progresses that is needed to run the course smoothly. Your VisuAlgo account will also be needed for taking NUS official VisuAlgo Online Quizzes and thus passing your account credentials to another person to do the Online Quiz on your behalf constitutes an academic offense. Your user account will be purged after the conclusion of the course unless you choose to keep your account (OPT-IN). Access to the full VisuAlgo database (with encrypted passwords) is limited to Prof Halim himself.

For other CS lecturers worldwide who have written to Steven, a VisuAlgo account (your (non-NUS) email address, you can use any display name, and encrypted password) is needed to distinguish your online credential versus the rest of the world. Your account will have CS lecturer specific features, namely the ability to see the hidden slides that contain (interesting) answers to the questions presented in the preceding slides before the hidden slides. You can also access Hard setting of the VisuAlgo Online Quizzes. You can freely use the material to enhance your data structures and algorithm classes. Note that there can be other CS lecturer specific features in the future.

For anyone with VisuAlgo account, you can remove your own account by yourself should you wish to no longer be associated with VisuAlgo tool.

Linked List Visualizer

by Von Vista

Adjustments:

Animation Speed

An Introduction to Linked List Data Structures

November 2, 2022 • Development

By Abdulazeez Abdulazeez Adeshina

Linked lists are one of the fundamental linear data structures alongside stacks, queues, arrays, and lists.

A linked list is a continuous list of nodes where a node is a block structure housing the node value and a pointer (or memory) address to the next node. Each node from the head node has a next pointer that keeps the address of the next node till it gets to the last node, which points to nothing.

Linked lists are used in web browsers to keep track of web pages visited and moves in multi-player board games. Linked lists also find usage in implementing other linear data structures and graphs, dynamic memory allocation, and performing arithmetic operations on long integers.

The connection from one node to another node differentiates linked lists from a regular list or array. Unlike the linked lists, arrays don’t keep track of their next or other values.

Here is a visual representation of a linked list:

Types of Linked Lists

The last node always points to NULL, except for circular linked lists.

There are three types of linked lists:

Singly-linked list

Doubly linked list.

• Circular linked list

You can derive other linked lists from the basic ones, e.g., circular doubly linked lists. This article teaches you how to implement the singly and doubly linked list and briefly discusses the circular linked list.

💡 In this article, we’ll use the Python programming language for the implementations.

You’re tasked with building a tool to retrieve documents connected to each other but stored at random memory locations. You’re puzzled as to what data structure to use to fit this use case, as arrays store documents sequentially. The good news is that you can use the singly linked list for this task.

A singly linked list is defined by its node. A singly linked list node has a value and the next pointer. The diagram below is an example of a singly linked list.

To implement the linked list, start with the node class:

In the code block above, the node class comprises two attributes:

• value : The value to be stored in the node.
• next : The pointer address to the next node. It has a default value of None ( NULL ).

Next, you need to implement the linked list class.

The linked list class

The linked list class is a wrapper for adding methods for node operations, such as appending a node, prepending a node, and deleting a node. Let’s say you want to append a node to the middle of a long chain of nodes. Doing so manually would look like this:

The process above is stressful. In a scenario where you need to perform this same operation for a couple of nodes, say 10, you have to do this manually every time. This operation brings forth unnecessary code bulkiness and complexity – known as space complexity. Having a linked list class with a method solves this all.

ℹ️ Each new variable defined in a program takes a significant amount of space. For example, a node costs 48 bytes of space, and a thousand nodes will cost 48000 bytes. Each time the program is executed, this amount of space is used for a single node initialization operation ignoring the internal space used by the linked list methods. Not only does this extra space slow down your application, but it also impacts the planet via poor eco-design .

The linked list class is independent. The LinkedList class implementation is:

In the code block above, the linked list class comprises three attributes:

• head : The head of the linked list, which is the first node.
• tail : The tail of the linked list, which is the last node.
• size : The size of the linked list.

Singly-linked list operations

The primary operations of a singly linked list include:

To perform the operations mentioned above, you need to define the methods under the linked list class. 

Before you begin to implement the primary operations, however, you will need to implement the __len__ method in the LinkedList class to return the length of your linked list stored in the self.size variable:

With the __len__ method implemented, you can return the size of the linked list with len(linkedlist) .

In simple words, traversal is a process of accessing elements stored in an object. A traversal operation is executed to print the elements in a linked list. 

Let’s implement our first method, __str__ , to print out the elements in the linked list:

The __str__ method in Python returns the string representation of an object. This method returns the node values in your linked list as a string separated by -> .

The insertion operation enables you to add nodes to your linked list. You can add nodes to your linked list by prepending the node, appending the node, or by adding nodes at specific positions in the linked list.

Prepending a node

The prepend method adds a new node at the head of the linked list, making it the new head node. The previous head node is automatically set as the next node after the new node. 

Implement the prepend method in the LinkedList class:

In the code block above, the prepend method takes an argument element , which is, in turn, passed to the Node class to form a node new_node . The new_node has its next pointer set to the head of the linked list self.head , and the linked list’s head node also points to the new node created. 

The method then checks if the tail of the linked list does not exist; if the tail doesn’t exist, it is set to the value of the head node.

Lastly, the method increments the size of the linked list.

Appending a node

The append method adds a new node to the end of the linked list. This method traverses the linked list until the next node pointer points to None – signifying the end of the linked list. The new node is attached to the tail’s node pointer, and the size of the linked list is incremented.

Implement the method in the linked list class:

Appending at a specific position

The last insertion operation is to append at a specific position. In this operation, a new node is added to the position specified. For example, if the linked list has four values, you can insert a new node at the third position. The node in the second position will have its next pointer pointing at the new node, and the new node points at the node originally in the third position.

In the LinkedList class, add the method:

With the insertion methods in place, create a new linked list and perform some operations:

The deletion operation involves removing a node from the linked list either from the head, tail or at a specified position. Implement the method for this operation in the LinkedList class:

In the code block above, the delete_node function performs three delete operations:

• Deleting the head node: If the position specified is 1, the head node is deleted by setting the value of the head node to the second node in the linked list.
• Deleting the tail node: If the position specified equals the number of nodes present in the linked list, the linked list is traversed to the end, and the second to the last node’s pointer is set to None to eliminate the tail node.
• Deleting a different node: If the position doesn’t match the head or tail nodes, the linked list is traversed until the specified position is reached. The node preceding the node at the specified position will have its next pointer set to the node located after the deleted node.

All of the operations above decrease the size of the linked list. An IndexError will be returned if a wrong position is passed to the method.

If you delete the second node you created earlier, the new linked list will be:

You’re tasked with implementing a new feature in a multiplayer board game (chess, checkers, tic-tac-toe, etc.) that enables a user to go back to their previous move. To implement this feature, you’ll likely need to use a doubly linked list data structure. 

A doubly linked list has two node pointers—one pointer pointing to the previous node and the other pointing to the next node.

Here is a graphical representation:

To implement a doubly linked list, implement the node class first:

The Node class above comprises three attributes:

• previous : The pointer address of the previous node.
• next : The pointer address of the next node.

The linked list class is a wrapper for adding methods for node operations. The LinkedList class definition for a doubly linked list is:

Doubly linked list operations

Just as before, the primary operations of a doubly linked list include:

To perform the above-mentioned operations, you need to define the methods under the linked list class.

Before you begin to implement the primary operations, implement the __len__ method in the LinkedList class to return the length of your linked list stored in the self.size variable:

This should look familiar, because it is the exact same method definition as a singly linked list.

In the code block above, the __str__ method will iterate through the linked list and store each node value separated by the delimiter <-> in a variable linkedlist which is returned when a linked list object is to be printed.

ℹ️ The __str__ and __len__ methods are the same for all linked lists. The only difference is the delimiter - > for singly and  <-> for the doubly linked list.

The insertion operation enables you to add nodes to your linked list either by prepending the node, appending the node, or adding the node at specific positions in the linked list.

The prepend method adds a new node at the head of the linked list. Implement the prepend method in the LinkedList class:

In the code block above, the method starts by creating a new node, new_node , with the argument passed to the prepend method. The method assigns the next pointer to the head node. It then checks if the linked list is not empty and assigns the head node’s previous pointer to the new node.

Once the pointer assignments are complete, the new node is assigned as the new head of the linked list.

The append method adds a new node to the end of the linked list. This method traverses the linked list until the next node pointer points to None (the end of the linked list). Once the end of the linked list is reached, the new node is attached to the tail’s node pointer, and the size of the linked list is incremented.

In the code block above, the append method checks if the tail of the linked list is None . If the tail is None , the method performs a prepend operation and exits.

However, if the tail exists, a new node is created and its previous pointer is set to the linked list tail node. The tail node as well sets its next pointer to the new node. Once the pointer assignment is completed, the new node is made the new tail by assigning the node to the self.tail variable.

Linked list nodes can be appended at a specified position. An example is inserting a new node at the fourth position in a linked list with five values.

The node before the position specified will have its next pointer pointing at the new node and its next pointer pointing at the node originally at the position specified.

In the code block above, the method first checks if the position is valid before proceeding. If the position is invalid, the method returns an IndexError .

If the position specified is the head node position 1, the method invokes the prepend method for the insertion. Otherwise, the method traverses the whole linked list until it gets to the position and performs the following:

• The method assigns the preceding node’s next pointer to the new node
• Sets the new node’s previous pointer to the preceding node
• Sets the new node’s next pointer to the current node
• Sets the current node’s previous pointer to the new node

The deletion operation removes a node from the linked list either from the head, tail or at a specified position. Implement the method for this operation in the LinkedList class:

• Deleting the head node: If the position specified is 1, the head node is deleted by setting both pointers to None , and the second node is assigned the head node.
• Deleting the tail node: If the position specified equals the number of nodes present in the linked list, the linked list is traversed to the end, and the second to the last node’s pointer is set to None to eliminate the tail node. The outgoing tail node’s pointers are also set to None respectively.
• Deleting a different node: If the position doesn’t match the head or tail nodes, the linked list is traversed until the specified position is reached. For example, to delete the third node in a 5-value linked list, the second node will have its next pointer pointing to the fourth node, and the fourth node’s previous pointer will now point to the second node.The node preceding the node at the position will have its next pointer set to the node of the next pointer of the node to be deleted. The next pointer after the node to be deleted will have its previous pointer pointing to the node preceding the current node to be deleted.

Circular linked lists

Circular linked lists are singly linked lists except that their last node points to the first node as opposed to None. As a result, the circular linked list does not have a tail node. Circular linked lists are commonly used to manage computing resources.

The circular linked list shares the same logic for insertion, traversal, and deletion as the singly linked list with the only difference being the assignment of the last node’s next pointer to the head node .

For example, the append method for the circular linked list is:

In the code block above, the prepend method first checks if the head node is not present in the linked list. If there’s no head node, the new node’s next pointer is set to itself, creating a circle. The circular linked list is implemented in the sandbox below to avoid repeating the implementation of the singular linked list.

Try it out in the CoderPad sandbox!

In this article, you have learned what linked lists are and how to implement singly and doubly linked lists. You can play with the sandboxes beneath this section to test the method you learned as well as implement new methods – the Coderpad Sandbox is an interactive sandbox for peer coding, live coding, and interviews.

Want more challenges? Create a sandbox and implement the reversal method for singly and doubly linked lists, create a tweet with your sandbox link, and tag CoderPad .

Learn Python practically and Get Certified .

Popular Tutorials

Popular examples, reference materials, learn python interactively, dsa introduction.

• What is an algorithm?
• Data Structure and Types
• Why learn DSA?
• Asymptotic Notations
• Master Theorem
• Divide and Conquer Algorithm

Data Structures (I)

• Types of Queue
• Circular Queue
• Priority Queue

Data Structures (II)

• Linked List
• Linked List Operations
• Types of Linked List
• Heap Data Structure
• Fibonacci Heap
• Decrease Key and Delete Node Operations on a Fibonacci Heap

Tree based DSA (I)

• Tree Data Structure
• Tree Traversal
• Binary Tree
• Full Binary Tree
• Perfect Binary Tree
• Complete Binary Tree
• Balanced Binary Tree
• Binary Search Tree

Tree based DSA (II)

• Insertion in a B-tree
• Deletion from a B-tree
• Insertion on a B+ Tree
• Deletion from a B+ Tree
• Red-Black Tree
• Red-Black Tree Insertion
• Red-Black Tree Deletion

Graph based DSA

• Graph Data Structure
• Spanning Tree
• Strongly Connected Components
• Adjacency Matrix
• Adjacency List
• DFS Algorithm
• Breadth-first Search
• Bellman Ford's Algorithm

Sorting and Searching Algorithms

• Bubble Sort
• Selection Sort
• Insertion Sort
• Counting Sort
• Bucket Sort
• Linear Search
• Binary Search

Greedy Algorithms

• Greedy Algorithm
• Ford-Fulkerson Algorithm
• Dijkstra's Algorithm
• Kruskal's Algorithm
• Prim's Algorithm
• Huffman Coding
• Dynamic Programming
• Floyd-Warshall Algorithm
• Longest Common Sequence

Other Algorithms

• Backtracking Algorithm
• Rabin-Karp Algorithm

DSA Tutorials

Types of Linked List - Singly linked, doubly linked and circular

Linked List Operations: Traverse, Insert and Delete

Circular Linked List

Doubly Linked List

• Tree Traversal - inorder, preorder and postorder

Linked list Data Structure

A linked list is a linear data structure that includes a series of connected nodes. Here, each node stores the data and the address of the next node. For example,

You have to start somewhere, so we give the address of the first node a special name called HEAD . Also, the last node in the linked list can be identified because its next portion points to NULL .

Linked lists can be of multiple types: singly , doubly , and circular linked list . In this article, we will focus on the singly linked list . To learn about other types, visit Types of Linked List .

Note: You might have played the game Treasure Hunt, where each clue includes the information about the next clue. That is how the linked list operates.

Representation of Linked List

Let's see how each node of the linked list is represented. Each node consists:

• A data item
• An address of another node

We wrap both the data item and the next node reference in a struct as:

Understanding the structure of a linked list node is the key to having a grasp on it.

Each struct node has a data item and a pointer to another struct node. Let us create a simple Linked List with three items to understand how this works.

If you didn't understand any of the lines above, all you need is a refresher on pointers and structs .

In just a few steps, we have created a simple linked list with three nodes.

The power of a linked list comes from the ability to break the chain and rejoin it. E.g. if you wanted to put an element 4 between 1 and 2, the steps would be:

• Create a new struct node and allocate memory to it.
• Add its data value as 4
• Point its next pointer to the struct node containing 2 as the data value
• Change the next pointer of "1" to the node we just created.

Doing something similar in an array would have required shifting the positions of all the subsequent elements.

In python and Java, the linked list can be implemented using classes as shown in the codes below .

• Linked List Utility

Lists are one of the most popular and efficient data structures, with implementation in every programming language like C, C++, Python, Java, and C#.

Apart from that, linked lists are a great way to learn how pointers work. By practicing how to manipulate linked lists, you can prepare yourself to learn more advanced data structures like graphs and trees.

Linked List Implementations in Python, Java, C, and C++ Examples

• Linked List Complexity

Time Complexity

Space Complexity: O(n)

Linked List Applications

• Dynamic memory allocation
• Implemented in stack and queue
• In undo functionality of softwares
• Hash tables, Graphs

Recommended Readings

1. tutorials.

• Linked List Operations (Traverse, Insert, Delete)
• Java LinkedList

2. Examples

• Get the middle element of Linked List in a single iteration
• Convert the Linked List into an Array and vice versa
• Detect loop in a Linked List

Table of Contents

• Introduction
• Linked List Representation
• How Next Node is Referenced?
• Python, Java and C/C++ Examples
• Linked List Application

Sorry about that.

Related Tutorials

DS & Algorithms

Queue (Linked List Implementaion)

Algorithm Visualizations

Navigation Menu

Search code, repositories, users, issues, pull requests..., provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

• Notifications

Visual represention of a Linked List

aes421/VisualLinkedList

Folders and files, repository files navigation.

Copyright (c) 2015 Ashley E. Stallings

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

This project is written using python 3. The purpose is to teach the fundamentals of linked list through visual representations explaining the code. Driver.py is what most users will want to run, since this file provides a driver to call all the different operations for the linked list. For specifics on commands use the keyword "help" when running the driver.

• Python 100.0%

Node Animation Speed:

Pointer Animation Speed:

Delete Animation Speed:

Linked List Visualization

• Formula Generator
• Code Generator
• Code Extender
• Database Query Writer
• Language Translator
• Pseudo Code Generator
• Regex Generator
• API Endpoint Generator
• Unit Test Writer
• Exception Handler
• Bug Detector
• Code Issues Solver
• Syntax Corrector
• Code Best Practices Checker

Visualizers

• Code Explainer
• Code Simplifier
• Code Visualizer
• Logic Visualizer
• Documentation Generator
• Dependency Resolver
• Complexity Estimator
• Data Structure Designer
• AI Big-O Analyzer
• Skills Advisor
• Tools Advisor
• Languages Advisor
• Project Advisor
• Algorithm Recommender
• Design Pattern Implementer
• Performance Predictor
• Statistical Method Recommender
• Variable Namer
• Threads New

Logic Visualizer | Python

Visual representation: linked list implementation.

This project provides a visual representation and implementation of a linked list data structure in Python. It includes two classes: Node and LinkedList. The Node class represents each individual node in the linked list, while the LinkedList class re...

Please explain how this code which implements a linked list in Python operates, especially while adding and removing elements.

Class: Node

• Represents each individual node in a linked list
• data : holds the value/data stored in the node
• next : holds a reference to the next node in the list

Class: LinkedList

• Represents the linked list as a whole
• head : references the first node in the list

Method: init

• Initializes an instance of the LinkedList class
• Sets the head property to None

Method: insert(data)

• Inserts a new node with the given data into the linked list
• Creates a new instance of the Node class with the given data
• If the list is empty (head is None), assigns the new node as the head
• Otherwise, traverses the list until the last node is reached
• Uses the next property to move to the next node
• Updates the next property of the last node to point to the new node

Method: delete(data)

• Deletes the first occurrence of a node with the given data from the linked list
• If the list is empty (head is None), returns
• If the first node contains the data, updates the head to point to the next node and returns
• Otherwise, iterates through the list until the data of the next node matches the given data
• Removes the reference to that node by updating the next property of the current node to skip the next node

Method: display()

• Returns a list of all the elements in the linked list
• Traverses the list from the head to the last node
• Stores the data of each node in a list and returns it

Usage Example:

• Create an instance of the LinkedList class
• Inserts nodes with data 'A', 'B', and 'C' into the linked list
• Deletes the node with data 'B'
• Displays the elements in the linked list
• Prints the resulting list: ['A', 'C']

Create your Thread using our flexible tools, share it with friends and colleagues.

Your current query will become the main foundation for the thread, which you can expand with other tools presented on our platform. We will help you choose tools so that your thread is structured and logically built.

Description

This project provides a visual representation and implementation of a linked list data structure in Python. The linked list is implemented using two classes: Node and LinkedList.

The Node class represents each individual node in the linked list and has two properties: data and next. The data property holds the value or data stored in the node, and the next property holds a reference to the next node in the list.

The LinkedList class represents the linked list as a whole and has one property: head. The head property references the first node in the list.

The LinkedList class also includes several methods. The init method initializes an instance of the LinkedList class and sets the head property to None.

The insert(data) method inserts a new node with the given data into the linked list. It creates a new instance of the Node class with the given data. If the list is empty (head is None), it assigns the new node as the head. Otherwise, it traverses the list until the last node is reached and uses the next property to move to the next node. It then updates the next property of the last node to point to the new node.

The delete(data) method deletes the first occurrence of a node with the given data from the linked list. If the list is empty (head is None), it returns. If the first node contains the data, it updates the head to point to the next node and returns. Otherwise, it iterates through the list until the data of the next node matches the given data. It removes the reference to that node by updating the next property of the current node to skip the next node.

The display() method returns a list of all the elements in the linked list. It traverses the list from the head to the last node and stores the data of each node in a list, which is then returned.

An example usage of the linked list implementation is provided in the code block at the bottom of the project description. It creates an instance of the LinkedList class, inserts nodes with data 'A', 'B', and 'C' into the linked list, deletes the node with data 'B', and displays the elements in the linked list. The resulting list is then printed.

More Logic Visualizers

Introduction to Linked Lists

Cs 106b: programming abstractions, autumn 2020, stanford university computer science department, lecturers: chris gregg and julie zelenski.

Announcements

• We are working on finalizing grades and should have them back early in the week.
• Assignment 5 is due on Wednesday . As usual, the grace period for submission will extend two days, until end-of-day Friday.

Today's Topics

• Structs and pointers
• Let's do it with a Vector
• Let's try it with links
• The Node struct

Lord of the Linked Lists

How is the stack implemented with a linked list.

• Linked List Queue implementation

Using pointers with class and struct objects

• Let's define a class (or it could be a struct) as follows: class Date { public: int day ; int month ; int year ; string dayOfWeek ; int daysInMonth (); };
• Pointers can point to a class or struct just like they can to any other variable: Date * dPtr = new Date ; // we now have a pointer to a Date object
• If we want to access the class variables and functions, we could do this: ( * dPtr ). day = 7 ; int numDays = ( * dPtr ). daysInMonth (); cout << ( * dPtr ). month << endl ;
• But, this notation is cumbersome, and the parentheses are necessary becasue the "dot" has a higher precedence than the * .
• So, there is a different, more intuitive syntax, called the arrow syntax: -> dPtr -> day = 7 ; int numDays = dPtr -> daysInMonth (); cout << dPtr -> month << endl ;
• Arrow notation, x -> var is equivalent to ( * x ). var , and we will use it exclusively when using classes and structs.

Can you architect a queue?

• Let's investigate building a queue from a Vector
• The following class definition for an integer queue would suffice for the enqueue and dequeue functions, with a Vector holding the data. class QueueInt { // in QueueInt.h public: QueueInt (); // constructor void enqueue ( int value ); // append a value int dequeue (); // return the first-in value private: Vector < int > data ; // member variables };
• Let's assume that we have the back of the queue on the left, and the front of the queue on the right. If we enqueue eight values, the vector would look like this: back front ↓ ↓ 1 2 3 4 5 6 7 8
• The dequeue operation is relatively straightforward: we just remove and return the element from the end, and the front is now at the previous index: back front ↓ ↓ 1 2 3 4 5 6 7 _
• But, enqueue is more involved. Because the back is on the left of the vector, we have to move all the elements over one, one at at time before placing our value into the vector. If we enqueue ( 9 ) on the vector, this is what happens: 1 2 3 4 5 6 7 7 1 2 3 4 5 6 6 7 1 2 3 4 5 5 6 7 1 2 3 4 4 5 6 7 1 2 3 3 4 5 6 7 1 2 2 3 4 5 6 7 1 1 2 3 4 5 6 7 9 1 2 3 4 5 6 7
• enqueue : O(n)
• dequeue : O(1)

And Now for Something Completely Different

• Let's use pointers to make things a bit more interesting.

• Now we have enqueued the 7 into the back of the queue! Our data points to the 7, which we have "pointed" to the 8.

• Remember, two pointers can point to the same value (in this case, both data and the 6 pointer).

• Oh, look, we've enqueued the 6 !
• We need to figure out what 8 points to. In this case, we will point 8 to nullptr , indicating that it is the end of the list. If we check 8's pointer and find that it is nullptr , then we are at the end of the list (or, in this case, the front of the queue). In the diagram, we just represent this with a slash through 8's pointer region.

• It turns out that this is the wrong way to build a queue with a linked list! We'll see at the end of the lecture a better way to do it by changing things just a bit.

Linked Lists

• What we've just examined is the beginning of a linked list
• A linked list is a chain of nodes
• Some piece of data that is stored in the sequence
• A link to the next node in the list

• Each element is stored separately from the rest.

Adding a node in the middle of a linked list

• To insert a node into the middle of a linked list, we first need to find the location where we are adding it – this can be a slow process because we have to travers from the beginning!

Removing a node in the middle of a linked list

• To remove a node into the middle of a linked list, we first need to find the location where we are adding it, as with insert.

Why linked lists?

• We can efficiently splice new elements into the list or remove existing elements anywhere in the list
• We never have to do a massive copy step
• Linked lists have many tradeoffs, and are not often the best data structure!

Linked lists in C++

• Let's take a look at building a linked list of strings
• In C++, we represent the node in the linked list as a struct , with two fields, a data field, and a next field: struct Node { string data ; /* ? */ next ;
• But, what is the type of next? It must point to another Node , so…it is a Node * type: struct Node { string data ; Node * next ; };
• The structure is defined recursively! The compiler can handle the fact that in the definition of the Node there is a Node * , becuase it knows it is simply a pointer. We could not recursively define the Node with an actual Node object inside the struct , as that would be impossible to realize.

Always draw pictures when you are building linked lists! This is critical to getting the hang of it.

Return of the King

• Return of the King clip

• Step 2: Light the fires! struct Tower { string name ; /* The name of this tower */ Tower * next ; /* Pointer to the next tower */ };
• Add the first tower: // add the first tower Tower * head = new Tower ; head -> name = "San Jose" ; head -> next = nullptr ;
• The main function: // main Tower * head = new Tower ; head -> name = "San Jose" ; head -> next = nullptr ; head = createTower ( "Santa Clara" , head ); head = createTower ( "Mountain View" , head ); head = createTower ( "Palo Alto" , head ); head = createTower ( "Menlo Park" , head ); head = createTower ( "Redwood City" , head ); head = createTower ( "Millbrae" , head ); head = createTower ( "Bayshore" , head ); head = createTower ( "San Francisco" , head );
• The createTower function: Tower * createTower ( string name , Tower * next ) { Tower * tp = new Tower ; tp -> name = name ; tp -> next = next ; return tp ; }
• The signal function (which is recursive!): void signal ( Tower * start ) { if ( start != nullptr ) { cout << "Lighting " << start -> name << endl ; signal ( start -> next ); } }
• We call the function with the head : signal ( head );

• The Node definition we've seen before: struct Node { int data ; Node * next ; };

• In other words: a linked list's elements must be pointed to, because we need to keep track of them. In our attempt above, we've lost access to the 8, becuase the only thing pointing at the 8 was head . If we reassign head to point to another object (the 7 in this case), we've broken the chain and lost 8. This is a common bug!

• Remember, head is not a Node . head is a pointer to a Node . Notice that head does not have a next – it's not an object, just a pointer.
• The statement temp -> next = head ; says, "give 7's next pointer the same data as head", which is what we want to do.

Stack pop ()

• This is a bug! Our linked list is fine, but we have a memory leak! We have left the 7 in memory and not returned it to the operating system with delete .

• Header, intStack . h :
• Class code, intStack . cpp

A Better Linked List Queue

• At the beginning of this topic, we discussed how to build a queue with a linked list. We had the back as the first element in the list, and the front as the second element. This led to O(1) behavior for enqueue, and O(n) behavior for dequeue. We can do better!
• If we hold a pointer to the front and to the back, and we make the front the first element in the list, and the back the last element in the list, we can successfully make a queue with O(1) behavior for both enqueue and dequeue.
• Here is the code, then we'll walk through some examples:
• intQueue . h
• intQueue . cpp :

4.3 Stacks and Queues

In this section, we introduce two closely-related data types for manipulating arbitrarily large collections of objects: the stack and the queue . Each is defined by two basic operations: insert a new item, and remove an item. When we insert an item, our intent is clear. But when we remove an item, which one do we choose? The rule used for a queue is to always remove the item that has been in the collection the most amount of time. This policy is known as first-in-first-out or FIFO . The rule used for a stack is to always remove the item that has been in the collection the least amount of time. This policy is known as last-in first-out or LIFO.

Pushdown Stacks

A pushdown stack (or just a stack ) is a collection that is based on the last-in-first-out (LIFO) policy. When you click a hyperlink, your browser displays the new page (and inserts it onto a stack). You can keep clicking on hyperlinks to visit new pages. You can always revisit the previous page by clicking the back button (remove it from a stack). The last-in-first-out policy offered by a pushdown stack provides just the behavior that you expect.

By tradition, we name the stack insert operation push and the stack remove operation pop . We also include a method to test whether the stack is empty. The following API summarizes the operations:

Python List (Resizing Array) Implementation of a Stack

Representing a stack with a Python list is a natural idea, but before reading further, it is worthwhile for you to think for a moment about how you would do so.

Naturally, you need an instance variable a[] to hold the stack items in a Python list. For efficiency, we store the items in order of their insertion because inserting and deleting from the end of a Python list takes constant amortized time per operation (whereas inserting and deleting from the front takes linear time per operation).

We could hardly hope for a simpler implementation of the Stack API than arraystack.py — all of the methods are one-liners! The instance variable is a Python list _a[] that hold the items in the stack in order of their insertion. To push an item, we append it to the end of the list using the += operator; to pop an item, we call the pop() method, which removes and returns the item from the end of the list; to determine the size of the stack, we call the built-in len() function. These operations preserve the following properties:

• The stack contains len(_a) items.
• The stack is empty when len(_a) is 0.
• The list _a[] contains the stack items, in order of their insertion.
• The item most recently inserted onto the stack (if nonempty) is _a[len(_a) - 1] .

The test client in arraystack.py allows for testing with an arbitrary sequence of operations: it does a push() for each string on standard input except the string consisting of a minus sign, for which it does a pop() . The diagram at right is a trace for the test file tobe.txt .

The primary characteristics of this implementation are that it uses space linear in the number of items in the stack and that the the push and pop operations take constant amortized time .

Linked-List Implementation of a Stack

Next, we consider a completely different way to implement a stack, using a fundamental data structure known as a linked list . Reuse of the word "list" here is a bit confusing, but we have no choice — linked lists have been around much longer than Python.

A linked list is a recursive data structure defined as follows: it is either empty (null) or a reference to a node having a reference to a linked list. The node in this definition is an abstract entity that might hold any kind of data, in addition to the node reference that characterizes its role in building linked lists.

With object-oriented programming, implementing linked lists is not difficult. We start with a class for the node abstraction:

class Node: def __init__(self, item, next): self.item = item self.next = next

An object of type Node has two instance variables: item (a reference to an item) and next (a reference to another Node object). The next instance variable characterizes the linked nature of the data structure. To emphasize that we are just using the Node class to structure the data, we define no methods other than the constructor. We also omit leading underscores from the names of the instance variables, thus indicating that it is permissible for code external to the data type (but still within our Stack implementation) to access those instance variables.

Now, from the recursive definition, we can represent a linked list with a reference to a Node object, which contains a reference to an item and a reference to another Node object, which contains a reference to an item and a reference to another Node object, and so forth. The final Node object in the linked list must indicate that it is, indeed, the final Node object. In Python, we accomplish that by assigning None to the next instance variable of the final Node object. Recall that None is a Python keyword — a variable assigned the value None references no object.

For example, to build a linked list that contains the items 'to' , 'be' , and 'or' , we execute this code:

third = Node('or', None) second = Node('be', third) first = Node('to', second)

For economy, we use the term link to refer to a Node reference. For simplicity, when the item is a string (as in our examples), we put it within the node rectangle (rather than using the more accurate rendition in which the node holds a reference to a string object, which is external to the node). This visual representation allows us to focus on the links.

Suppose that you want to remove the first node from a linked list. This operation is easy: simply assign to first the value first.next . Normally, you would retrieve the item (by assigning it to some variable) before doing this assignment, because once you change the variable first , you may lose any access to the node to which it was referring previously. Typically, the Node object becomes an orphan, and Python's memory management system eventually reclaims it.

Now, suppose that you want to insert a new node into a linked list. The easiest place to do so is at the beginning of the linked list. For example, to insert the string 'not' at the beginning of a given linked list whose first node is first , we save first in a variable oldFirst ; create a new Node whose item instance variable is 'not' and whose next instance variable is oldFirst ; and assign first to refer to that new Node .

Those two operations take constant time; their efficiency is independent of the length of the list.

Implementing stacks with linked lists.

Linked list traversal.

For stacks, linked lists are significant because they allow us to implement the push() and pop() methods in constant time in the worst case, while using only a small constant factor of extra space (for the links). Still, Python programmers usually prefer Python lists (resizing arrays), primarily because of the substantial Python overhead for user-defined types like our linked-list Node .

Stack Applications

Pushdown stacks play an essential role in computation. Some examples illustrate.

Arithmetic expressions.

( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )

How does Python do this calculation? We can address the essential ideas just by composing a Python program that can take a string as input (the expression) and produce the number represented by the expression as output. For simplicity, we begin with the following explicit recursive definition: an arithmetic expression is either a number or a left parenthesis followed by an arithmetic expression followed by an operator followed by another arithmetic expression followed by a right parenthesis. For simplicity, this definition applies to fully parenthesized arithmetic expressions, which specifies precisely which operators apply to which operands. For specificity, we support the familiar binary operators *, +, and -, as well as a square-root operator sqrt that takes only one argument.

Arithmetic expression evaluation.

• Push operands onto the operand stack.
• Push operators onto the operator stack.
• Ignore left parentheses.
• On encountering a right parenthesis, pop an operator, pop the requisite number of operands, and push onto the operand stack the result of applying that operator to those operands.

After the final right parenthesis has been processed, there is one value on the stack, which is the value of the expression. The program evaluate.py is an implementation of this algorithm. Try running it with expression1.txt and expression2.txt .

Stack-based programming languages.

( 1 ( ( 2 3 + ) ( 4 5 * ) * ) + )

In other words, we can put each operator after its two operands instead of between them. In such an expression, each right parenthesis immediately follows an operator so we can ignore both kinds of parentheses, writing the expressions as follows:

1 2 3 + 4 5 * * +

This notation is known as reverse Polish notation , or postfix . To evaluate a postfix expression, we use one stack . Proceeding from left to right, taking these entities one at a time, we manipulate the stacks according to just two possible cases:

• On encountering an operator, pop the requisite number of operands and push onto the operand stack the result of applying the operator to those operands.

Again, this process leaves one value on the stack, which is the value of the expression. This representation is so simple that some programming languages, such as Forth (a scientific programming language) and PostScript (a page description language that is used on most printers) use explicit stacks.

Function-call abstraction.

Fifo queues.

A FIFO queue (or just a queue) is a collection that is based on the first-in first-out (FIFO) policy. Queues are a natural model for so many everyday phenomena that their properties were studied in detail even before the advent of computers.

As usual, we begin by articulating an API. Again by tradition, we name the queue insert operation enqueue and the remove operation dequeue , as indicated in the API below.

Applying our knowledge from stacks, we can use either Python lists (resizing arrays) or linked lists to develop implementations where the operations take constant time and the memory associated with the queue grows and shrinks with the number of elements in the queue.

Linked-list implementation.

The program linkedqueue.py is a linked-list implementation of Queue that has the same performance properties as Stack : all of the methods are constant-time operations, and space usage is linear in the number of items on the queue.

Resizing array implementation.

Random queues., queue applications.

In the past century, FIFO queues proved to be accurate and useful models in a broad variety of applications. A field of mathematics known as queuing theory has been used with great success to help understand and control complex systems of all kinds. Understanding and controlling such a complex system involves solid implementations of the queue abstraction, application of mathematical results of queueing theory, and simulation studies involving both. We consider next a classic example to give a flavor of this process.

M/M/1 queue.

• There is one server — a FIFO queue.
• Interarrival times to a queue obey an exponential distribution with rate λ per minute.
• Service times from a nonempty queue obey an exponential distribution with rate μ per minute.

In practical applications, people are interested in the effect of the parameters λ and μ on various properties of the queue. For M/M/1 queues, it is known that the average number of customers in the system L is λ / (μ - λ), and the average time a customer spends in the system W is 1 / (μ - λ). These formulas confirm that the wait time (and queue length) grows without bound as λ approaches μ. They also obey a general rule known as Little's law : the average number of customers in the system is λ times the average time a customer spends in the system ( L - λ W ) for many types of queues.

The program mm1queue.py is a Queue client that you can use to validate these sorts of mathematical results. It is a simple example of an event-based simulation : we generate events that take place at particular times and adjust our data structures accordingly for the events, simulating what happens at the time they occur. See the textbook for details. From a practical point of view, one of the most important characteristics of the process, which you can discover for yourself by running mm1queue.py for various values of the parameters λ and μ, is that the average time a customer spends in the system (and the average number of customers in the system) can increase dramatically when the service rate approaches the arrival rate.

% python mm1queue.py .167 .25 % python mm1queue.py .167 .20

Resource allocation.

Central authorities often use a random policy, where the assignments are based on random choice. An even better policy is to choose a random sample of servers and assign a new item to the one that has smallest number of items. But how big a sample should we take?

The program loadbalance.py is a simulation of the sampling policy, which we can use to study this question. This program makes good use of the RandomQueue data type (see the "Random queue" creative exercise at the end of this section) to provide an easily understood program that we can use for experimentation. The simulation maintains a random queue of queues and builds the computation around an inner loop where each new request for service goes on the smallest of a sample of queues, using the sample() method from RandomQueue to randomly sample queues. The surprising end result is that samples of size 2 lead to near-perfect balancing, so there is no point in taking larger samples.

% python loadbalance.py 50 500 1 % python loadbalance.py 50 500 2

Q. When should I call the _Node constructor?

A. Just as with any other class, you should call the _Node constructor when you want to create a new _Node object (a new node in the linked list). You should not use it to create a new reference to an existing _Node object. For example, the code

oldfirst = _Node(item, next) oldfirst = first

creates a new _Node object, then immediately loses track of the only reference to it. This code does not result in an error, but it is a bit untidy to create orphans for no reason.

Q. Why not define Node as a stand-alone class in a separate file named node.py ?

A. By defining _Node in the same file as linkedstack.py or linkedqueue.py and giving it a name that begins with an underscore, we encourage clients of the Stack or Queue classes not to use the _Node class directly. Our intention is that the _Node objects be used only in the linkedstack.py or linkedqueue.py implementations, not in other clients.

Q. Should a client be allowed to insert the item None onto a stack or queue?

A. This question arises frequently when implementing collections in Python. Our implementations do permit the insertion of any object, including None .

Q. Are there standard Python modules for stacks and queues?

A. Not really. As noted earlier in this section, Python's built-in list data type has operations that make it is easy to efficiently implement a stack using a list. But the list data type also needs many additional methods that are not normally associated with a stack, such as indexed access and deleting an arbitrary item. The prime advantage of restricting ourselves to the set of operations that we need (and only those operations) is that it makes it easier to develop an implementation that can provide the best possible performance guarantees for those operations. Python also includes a data type collections.deque that implements a mutable sequence of items with efficient insertion and deletion to either the front or the back.

Q. Why not have a single data type that implements methods to insert an item, remove the most recently inserted item, remove the least recently inserted item, remove a random item, iterate over the items, return the number of items in the collection, and whatever other operations we might desire? Then we could get them all implemented in a single class that could be used by many clien

A. This is an example of a wide interface , which, as we pointed out in Section 3.3, should be avoided. As just mentioned, one reason to avoid wide interfaces is that it is difficult to construct implementations that are efficient for all operations. A more important reason is that narrow interfaces enforce a certain discipline on your programs, which makes client code much easier to understand. If one client uses Stack and another uses Queue , we have a good idea that the LIFO discipline is important to the first and the FIFO discipline is important to the second. Another approach is to use inheritance to try to encapsulate operations that are common to all collections. However, such implementations are best left for experts, whereas any programmer can learn to build implementations such as Stack and Queue .

Q. Is there any way that I can compose a client that uses both arraystack.py and linkedstack.py in the same program?

A. Yes, the easiest way is to add an as clause to the import statement, as below. In effect, this kind of import statement creates an alias for the name of the class and your code can then use that alias instead of the name of the class.

from arraystack import Stack as ArrayStack from linkedstack import Stack as LinkedStack ... stack1 = ArrayStack() stack2 = LinkedStack()

Give the output written by arraystack.py for the following input:

it was - the best - of times - - - it was - the - -

Give the contents and length of the array for arraystack.py after each operation for the following input:

Suppose that a client performs an intermixed sequence of push and pop operations on a Stack . The push operations put the integers 0 through 9 in order onto the stack; the pop operations write the return value. Which of the following sequence(s) could not occur?

4 3 2 1 0 9 8 7 6 5 4 6 8 7 5 3 2 9 0 1 2 5 6 7 4 8 9 3 1 0 4 3 2 1 0 5 6 7 8 9 1 2 3 4 5 6 9 8 7 0 0 4 6 5 3 8 1 7 2 9 1 4 7 9 8 6 5 3 0 2 2 1 4 3 6 5 8 7 9 0

Compose a stack client reverse.py that reads in strings from standard input and writes them in reverse order to standard output. Compose a stack client parentheses.py that reads in a text stream from standard input and uses a stack to determine whether its parentheses are properly balanced. For example, your program should write True for [()]{}{[()()]()} and False for [(]) .

Add the method __len__() to the Stack class in linkedstack.py .

Add a method peek() to the Stack class in arraystack.py that returns the most recently inserted item on the stack (without popping it).

What does the following code fragment write when n is 50? Give a high-level description of what the code fragment does for a given positive integer n .

stack = Stack() while n > 0: stack.push(n % 2) n /= 2 while not stack.isEmpty(): stdio.write(stack.pop()) stdio.writeln()

Solution : It writes the binary representation of n ( 110010 when n is 50).

What does the following code fragment do to the queue queue ?

stack = Stack() while not queue.isEmpty(): stack.push(queue.dequeue()) while not stack.isEmpty(): queue.enqueue(stack.pop())

Draw an object-level trace diagram for the three-node example used to introduce linked lists in this section.

Compose a program that takes from standard input an expression without left parentheses and writes the equivalent infix expression with the parentheses inserted. For example, given the input

1 + 2 ) * 3 - 4 ) * 5 - 6 ) ) )

your program should write

( ( 1 + 2 ) * ( ( 3 - 4 ) * ( 5 - 6 ) )

Compose a filter infixtopostfix.py that converts a fully parenthesized arithmetic expression from infix to postfix.

Compose a program evaluatepostfix.py that reads a postfix expression from standard input, evaluates it, and writes the value to standard output. (Piping the output of your program from the previous exercise to this program gives equivalent behavior to evaluate.py .)

Suppose that a client performs an intermixed sequence of enqueue and dequeue operations on a Queue . The enqueue operations put the integers 0 through 9 in order onto the queue; the dequeue operations write the return value. Which of the following sequence(s) could not occur?

0 1 2 3 4 5 6 7 8 9 4 6 8 7 5 3 2 9 0 1 2 5 6 7 4 8 9 3 1 0 4 3 2 1 0 5 6 7 8 9

Compose a Queue client that takes a command-line argument k writes the k th from the last string found on standard input.

Give the running time of each operation in the following Queue class, where the item least recently inserted is at _a[0] .

class Queue: def __init__(self): self._a = [] def isEmpty(self): return len(self._a) == 0 def __len__(self): return len(self._a) def enqueue(self, item): self._a += [item] def dequeue(self): return self._a.pop(0)

Give the running time of each operation in the following Queue class, where the item most recently inserted is at _a[0] .

class Queue: def __init__(self): self._a = [] def isEmpty(self): return len(self._a) == 0 def __len__(self): return len(self._a) def enqueue(self, item): self._a.insert(0, item) def dequeue(self): return self._a.pop()

Modify mm1queue.py to make a program md1queue.py that simulates a queue for which the service times are fixed (deterministic) at rate of μ. Verify Little's law empirically for this model.

Linked List Exercises

The following exercises are intended to give you experience in working with linked lists. The easiest way to work them is to make drawings using the visual representation described in the text.

Suppose x is a linked-list node. What is the effect of the following code fragment?

x.next = x.next.next

Solution : Deletes from the list the node immediately following x .

Compose a function find() that takes the first node in a linked list and an object key as arguments and returns True if some node in the list has key as its item field, and False otherwise.

Compose a function delete() that takes the first node in a linked list and an integer k as arguments and deletes the k th element in a linked list, if it exists.

Suppose that x is a linked-list node. What is the effect of the following code fragment?

t.next = x.next x.next = t

Solution : Inserts node t immediately after node x .

Why does the following code fragment not have the same effect as the code fragment in the previous question?

x.next = t t.next = x.next

Solution : When it comes time to update t.next , x.next is no longer the original node following x , but is instead t itself!

Compose a function removeAfter() that takes a linked-list node as an argument and removes the node following the given one (and does nothing if the argument or the next field in the argument node is None ).

Compose a function copy() that takes a linked-list node as an argument and creates a new linked list with the same sequence of items, without destroying the original linked list.

Compose a function remove() that takes a linked-list node and an object item as arguments and removes every node in the list whose item is item.

Compose a function listmax() that takes the first node in a linked list as an argument and returns the value of the maximum item in the list. Assume that the items are comparable, and return None if the list is empty.

Develop a recursive solution to the previous question.

Compose a function that takes the first node in a linked list as an argument and reverses the list, returning the first node in the result.

Iterative solution : To accomplish this task, we maintain references to three consecutive nodes in the linked list: reverse , first , and second . At each iteration, we extract the node first from the original linked list and insert it at the beginning of the reversed list. We maintain the invariant that first is the first node of what's left of the original list, second is the second node of what's left of the original list, and reverse is the first node of the resulting reversed list.

def reverse(first): reverse = None while first is not None: second = first.next first.next = reverse reverse = first first = second return reverse

When composing code involving linked lists, we must always be careful to properly handle the exceptional cases (when the linked list is empty, when the list has only one or two nodes) and the boundary cases (dealing with the first or last items). This is usually much trickier than handling the normal cases.

Compose a recursive function to write the elements of a linked list in reverse order. Do not modify any of the links. Easy : Use quadratic time, constant extra space. Also easy : Use linear time, linear extra space. Not so easy : Develop a divide-and-conquer algorithm that uses linearithmic time and logarithmic extra space.

Quadratic time, constant space solution : We recursively reverse the part of the list starting at the second node, and then carefully append the first element to the end.

def reverse(first): if first is None: return None if first.next is None: return first second = first.next rest = reverse(second) second.next = first first.next = None return rest

Compose a recursive function to randomly shuffle the elements of a linked list by modifying the links. Easy : Use quadratic time, constant extra space. Not so easy : Develop a divide-and-conquer algorithm that takes linearithmic time and uses logarithmic extra memory. For the "merging" step, see the "Riffle shuffle" creative exercise at the end of Section 1.4.

Creative Exercises

Deque. A double-ended queue or deque (pronounced "deck") is a combination of a stack and a queue. Compose a class Deque that uses a linked list to implement this API:

Josephus problem. In the Josephus problem from antiquity, n people are in dire straits and agree to the following strategy to reduce the population. They arrange themselves in a circle (at positions numbered from 0 to n -1) and proceed around the circle, eliminating every m person until only one person is left. Legend has it that Josephus figured out where to sit to avoid being eliminated. Compose a Queue client josephus.py that takes n and m from the command line and writes the order in which people are eliminated (and thus would show Josephus where to sit in the circle).

% python josephus.py 7 2 1 3 5 0 4 2 6

Merging two sorted queues. Given two queues with strings in ascending order, move all of the strings to a third queue so that the third queue ends up with the strings in ascending order.

Nonrecursive mergesort. Given n strings, create n queues, each containing one of the strings. Create a queue of the n queues. Then, repeatedly apply the sorted merging operation to the first two queues and reinsert the merged queue at the end. Repeat until the queue of queues contains only one queue.

Delete ith element. Implement a class that supports the following API:

First, develop an implementation that uses a Python list (resizing array) implementation, and then develop one that uses a linked-list implementation. (See the "Generalized queue" creative exercise at the end of Section 4.4 for a more efficient implementation that uses a binary search tree.)

Queue with two stacks. Show how to implement a queue using two stacks (and only a constant amount of extra memory) so that each queue operations uses a constant amortized number of stack operations.

Ring buffer. A ring buffer, or circular queue, is a FIFO data structure of a fixed capacity n . It is useful for transferring data between asynchronous processes or for storing log files. When the buffer is empty, the consumer waits until data is deposited; when the buffer is full, the producer waits to deposit data. Develop an API for a ring buffer and an implementation that uses an array representation (with circular wrap-around).

Move-to-front. Read in a sequence of characters from standard input and maintain the characters in a linked list with no duplicates. When you read in a previously unseen character, insert it at the front of the list. When you read in a duplicate character, delete it from the list and reinsert it at the beginning. Name your program movetofront.py : it implements the well known move-to-front strategy, which is useful for caching, data compression, and many other applications where items that have been recently accessed are more likely to be reaccessed.

Random queue. A random queue stores a collection of items as per this API:

Compose a class RandomQueue that implements this API. Hint : Use a Python list (resizing array) representation, as in arraystack.py . To remove an item, swap one at a random position (indexed 0 through n -1) with the one at the last position (index n -1). Then delete and return the last object. Compose a client that writes a deck of cards in random order using RandomQueue .

Solution : See randomqueue.py .

Topological sort. You have to sequence the order of n jobs that are numbered from 0 to n -1 on a server. Some of the jobs must complete before others can begin. Compose a program topologicalsorter.py that takes n as a command-line argument and a sequence on standard input of ordered pairs of jobs i j , and then writes a sequence of integers such that for each pair i j in the input, job i appears before job j . Use the following algorithm: First, from the input, build, for each job, (1) a queue of the jobs that must follow it and (2) its indegree (the number of jobs that must come before it). Then, build a queue of all nodes whose indegree is 0 and repeatedly delete some job with zero indegree, maintaining all the data structures. This process has many applications; for example, you can use it to model course prerequisites for your major so that you can find a sequence of courses to take so that you can graduate.

Text editor buffer. Develop a data type for a buffer in a text editor that implements the following API:

Hint : Use two stacks.

Copy a stack. Create a copy() method for the linked-list implementation of Stack so that

stack2 = stack1.copy()

makes stack2 a reference to a new and independent copy of the stack stack1 . You should be able to push and pop from either stack1 or stack2 without influencing the other.

Copy a queue. Create a copy() method for the linked-list implementation of Queue so that

queue2 = queue1.copy()

makes queue2 a reference to a new and independent copy of the queue queue1 . Hint : Delete all of the items from queue1 and add these items to both queue1 and queue2 .

Stack with explicit resizing array. Implement a stack using an explicit resizing array: initialize an empty stack by using an array of length 1 as an instance variable; double the length of the array when it becomes full and halve the length of the array when it becomes one-fourth full.

class Stack: def __init__(self): self._a = [None] self._n = 0 def isEmpty(self): return self._n == 0 def __len__(self): return self._n def _resize(self, capacity): temp = stdarray.create1D(capacity) for i in range(self._n): temp[i] = self._a[i] self._a = temp def push(self, item): if self._n == len(self._a): self._resize(2 * self._n) self._a[self._n] = item self._n += 1 def pop(self): self._n -= 1 item = self._a[self._n] self._a[self._n] = None if (self._n > 0) and (self._n == len(self._a) // 4): self._resize(self._n // 2) return item

Queue with explicit resizing array. Implement a queue using an explicit resizing array so that all operations take constant amortized time. Hint : The challenge is that the items will "crawl across" the array as items are added to and removed from the queue. Use modular arithmetic to maintain the array indices of the items at the front and back of the queue.

stdin stdout n lo hi a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] 0 0 0 None to 1 0 1 to None be 2 0 2 to be or 3 0 3 to be or None not 4 0 4 to be or not to 5 0 5 to be or not to None None None - to 4 1 4 None be or not to None None None be 5 1 6 None be or not to be None None - be 4 2 6 None None or not to be None None - or 3 3 6 None None None not to be None None that 4 3 7 None None None not to be that None

Errata: The last two rows should be:

None None None not to be None None None None None not to be that None

Solution : See arrayqueue.py .

Queue simulations. Study what happens when you modify mm1queue.py to use a stack instead of a queue. Does Little's law hold? Answer the same question for a random queue. Plot histograms and compare the standard deviations of the waiting times.

Load-balancing simulations. Revise loadbalance.py to write the average queue length and the maximum queue length instead of plotting the histogram, and use it to run simulations for 1 million items on 100000 queues. Write the average value of the maximum queue length for 100 trials each with sample sizes 1, 2, 3, and 4. Do your experiments validate the conclusion drawn in the text about using a sample of size 2?

Listing files. A folder is a list of files and subfolders. Compose a program that takes the name of a folder as a command-line argument and writes all of the file names contained in that folder, with the contents of each folder recursively listed (indented) under that folder's name. Hint : Use a queue, and see the listdir() function defined in Python's os module.

Linked lists

Introduction.

Linked lists are the best and simplest example of a dynamic data structure that uses pointers for its implementation. However, understanding pointers is crucial to understanding how linked lists work, so if you've skipped the pointers tutorial, you should go back and redo it. You must also be familiar with dynamic memory allocation and structures.

Essentially, linked lists function as an array that can grow and shrink as needed, from any point in the array.

Linked lists have a few advantages over arrays:

• Items can be added or removed from the middle of the list
• There is no need to define an initial size

However, linked lists also have a few disadvantages:

• There is no "random" access - it is impossible to reach the nth item in the array without first iterating over all items up until that item. This means we have to start from the beginning of the list and count how many times we advance in the list until we get to the desired item.
• Dynamic memory allocation and pointers are required, which complicates the code and increases the risk of memory leaks and segment faults.
• Linked lists have a much larger overhead over arrays, since linked list items are dynamically allocated (which is less efficient in memory usage) and each item in the list also must store an additional pointer.

What is a linked list?

A linked list is a set of dynamically allocated nodes, arranged in such a way that each node contains one value and one pointer. The pointer always points to the next member of the list. If the pointer is nullptr , then it is the last node in the list.

Let's define a linked list node:

A linked list is held using a pointer which points to the first item of the linked list called "head" and a pointer which points to the last item of the linked list called "tail". If that pointer (the "tail") is also nullptr , then the list is considered to be empty.

Let's define a linked list:

Adding an item (to the end of the linked list)

Now we can use the nodes. Let's create a method createNode to create the first item of the linked list. The process of creating node is as follows. We need a pointer of a Node type (which we defined) and we will insert the value in its data field. The next field of Node would be declared as nullptr as it would be the last node of linked list.

There is a special case, which we need to check for namely when the linked list is empty. As we know, head points to the first node? It means if the head is equal to nullptr then we can conclude that the linked list is empty.

If there is just one node (which we are going to create) in a linked lists, then both head and tail will point to this element.

If a linked list is already created, the new node should be inserted at the end of the linked list. We know that tail points to the last node. Therefore, the newly created node will be next to the node tail is pointing to.

The creation of a new node at the end of linked list has two steps:

Linking the newly created node to tail . Means passing the address of a new node to the next pointer of tail .

The tail pointer should always point to the last node. So we will make our tail pointer equal to a new node.

Let's add this method to the LinkedList class:

Iterating over a list

Let's build a function that prints out all the items of a list ( printList ). To do this, we need to use a current pointer that will keep track of the node we are currently printing. After printing the value of the node, we set the current pointer to the next node, and print again, until we've reached the end of the list (the next node is nullptr ).

Inserting a new node in the linked list is called insertion.

A new node is created and inserted in the linked list.

There are three cases considered while inserting a node:

• Insertion at the start
• Insertion at the end
• Insertion at a particular position

Insertion an item at the start of the list (pushing to the list)

To add to the beginning of the list, we will need to do the following three steps:

• Create a new item and set its value
• Link the new item to point to the head of the list
• Set the head of the list to be our new item

This will effectively create a new head to the list with a new value, and keep the rest of the list linked to it.

Since we use a method to do this operation, we want to be able to modify the head variable. To do this, we must pass a pointer to the pointer variable (a double pointer) so we will be able to modify the pointer itself.

Insertion at the End

The insertion of a node at the end of a linked list is the same as we have done in node creation function. If you noticed then, we inserted the newly created node at the end of the linked list. So this process is the same.

Insertion at Particular Position

The insertion of a new node at a particular position is slightly more difficult. In this case, we don’t disturb the head and tail nodes. Rather, a new node is inserted between two consecutive nodes. So, these two nodes should be accessible by our code. We call one node as current and the other as previous , and the new node is placed between them.

The new node can be inserted between the previous and current node by just performing two steps:

• Pass the address of the new node in the next field of the previous node.
• Pass the address of the current node in the next field of the new node.

We will access these nodes by asking the user at what position he wants to insert the new node. Then, we will start a loop to reach those specific nodes. We initialized our current node by the head and move through the linked list. At the end, we would find two consecutive nodes.

C++ code for insertion of node would be as follows:

So, you have become familiar with linked list creation. Now, it’s time to do some manipulation on the linked list created. Linked lists provide us the great feature of deleting a node. The process of deletion is also easy to implement. The basic structure is to declare a temporary pointer which points the node to be deleted. Then a little bit of working on links of nodes. There are also three cases in which a node can be deleted:

• Deletion at the start
• Deletion at the end
• Deletion at a particular position

Deletion of the first item (popping from the linked list)

To pop a variable, we will need to perform three steps:

• Take the next item that the head points to and save it
• Free the head item
• Set the head to be the next item that we've stored on the side

Here is the code:

Deletion of the last item of the list

Removing the last item from a list is very similar to adding it to the end of the list, but with one big exception - since we have to change one item before the last item, we actually have to look two items ahead and see if the next item is the last one in the list:

Removing a specific item

To remove a specific item from the list, either by its index from the beginning of the list or by its value, we will need to go over all the items, continuously looking ahead to find out if we've reached the node before the item we wish to remove. This is because we need to change the location to where the previous node points to as well.

Here is the algorithm:

• Iterate to the node before the node we wish to delete
• Save the node we wish to delete in a temporary pointer
• Set the previous node's next pointer to point to the node after the node we wish to delete
• Delete the node using the temporary pointer

There are a few edge cases we need to take care of, so make sure you understand the code.

Note: This tutorial is inspired by and some content is taken from the following tutorial: https://www.codementor.io/codementorteam/a-comprehensive-guide-to-implementation-of-singly-linked-list-using-c_plus_plus-ondlm5azr

You must implement the function removeByValue which removes the first item in the list which has the value value .

Coding for Kids is an online interactive tutorial that teaches your kids how to code while playing!

Receive a 50% discount code by using the promo code:

Start now and play the first chapter for free, without signing up.