{"id":9366,"date":"2020-11-25T06:39:27","date_gmt":"2020-11-25T06:39:27","guid":{"rendered":"https:\/\/www.askpython.com\/?p=9366"},"modified":"2020-11-30T09:00:36","modified_gmt":"2020-11-30T09:00:36","slug":"linked-lists-in-python","status":"publish","type":"post","link":"https:\/\/www.askpython.com\/python\/examples\/linked-lists-in-python","title":{"rendered":"Linked Lists in Python"},"content":{"rendered":"\n<p><strong>Linked lists<\/strong> in Python are one of the most interesting abstract data types that have continued to stay in popularity since the C\/C++ days. In this article, we&#8217;ll learn how to implement a Linked list in Python from scratch.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">What is a Linked List?<\/h2>\n\n\n\n<p>A<strong> <em>linked list<\/em><\/strong> is a linear data structure where each element is a separate object. The elements of a linked list, unlike an array, are not stored together in the memory. <\/p>\n\n\n\n<p>Each element of the linked list points to the element after it. Here points mean that each element<strong> stores the address of the next element. <\/strong><\/p>\n\n\n\n<p>While traversing a linked list we use these pointers to jump from one node to the next. <\/p>\n\n\n\n<p>For each linked list, there are a two elements that need to be considered:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>The nodes &#8211; We handle them by creating a node <a href=\"https:\/\/www.askpython.com\/python\/oops\/python-classes-objects\" class=\"rank-math-link\">class<\/a><\/li><li>The connection between nodes &#8211; We will handle this with the variables and <a href=\"https:\/\/www.askpython.com\/python\/difference-between-python-list-vs-array\" class=\"rank-math-link\">lists in Python<\/a>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">How to Create a Linked List in Python?<\/h2>\n\n\n\n<p>Let&#8217;s go over the steps to create a linked list in Python.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Create the Node Class<\/h2>\n\n\n\n<p>To create our own linked list we need to define a node class. Before we define a node class, we need to think about what fields should the class have. <\/p>\n\n\n\n<p>A linked list node is supposed to store two things. These are :<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li><strong>Data<\/strong><\/li><li><strong>Address of the next node <\/strong><\/li><\/ol>\n\n\n\n<p>Let&#8217;s define a node class with these two fields. <\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\nclass Node(object):\n\n    def __init__(self, data=None, next_node=None):\n        self.data = data\n        self.next_node = next_node\n\n<\/pre><\/div>\n\n\n<h2 class=\"wp-block-heading\">Create the Linked-List class <\/h2>\n\n\n\n<p>Let&#8217;s make another class that will initialize an empty node for creating a linked list. <\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\nclass LinkedList(object):\n    def __init__(self, head=None):\n        self.head = head\n<\/pre><\/div>\n\n\n<p>There are a few important functions that will be held within this class. Let&#8217;s go over the purpose and the definition for each of these classes.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">1. Function to print the list<\/h3>\n\n\n\n<p>Let&#8217;s write a function to print our linked list. To <a href=\"https:\/\/www.askpython.com\/python\/built-in-methods\/python-print-function\" class=\"rank-math-link\">print<\/a> the linked list we need to traverse through the entire list and keep printing the data from each node.<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\ndef printList(self): \n        temp = self.head \n        while (temp): \n            print (temp.data, &quot; -&gt; &quot;, end = &#039;&#039;) \n            temp = temp.next_node\n        print(&quot;&quot;)\n<\/pre><\/div>\n\n\n<h3 class=\"wp-block-heading\">2. Get size of the list <\/h3>\n\n\n\n<p>Let&#8217;s write a function that returns the size of the linked list. To calculate the size, we need to traverse through the entire list and keep a counter while doing so. <\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\ndef size(self):\n     current = self.head\n     count = 0\n     while current:\n        count += 1\n        current = current.next_node\n     return count\n<\/pre><\/div>\n\n\n<p>This function will return the size of the linked list. <\/p>\n\n\n\n<h3 class=\"wp-block-heading\">3. Insert a new node at the head<\/h3>\n\n\n\n<p>Let&#8217;s write a function to insert a new node at the head. <\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: plain; title: ; notranslate\" title=\"\">\ndef insert_at_head(self, data):\n      new_node = Node(data)\n      new_node.next_node = self.head\n      self.head = new_node\n<\/pre><\/div>\n\n\n<p>This will create a new node with the data and add it before the head. It then points the head of the linked list to this new node.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">4. Get Next node<\/h3>\n\n\n\n<p>The function to get next node is given below :<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\n def get_next_node (self,node):\n      return node.next_node.data\n<\/pre><\/div>\n\n\n<h2 class=\"wp-block-heading\">Create a New Linked List<\/h2>\n\n\n\n<p>Let&#8217;s write the main function and create a linked list using the class we created above. <\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\nllist = LinkedList() \n<\/pre><\/div>\n\n\n<p>This line of code initializes the llist <a href=\"https:\/\/www.askpython.com\/python\/oops\/python-classes-objects\" class=\"rank-math-link\">object<\/a> with an empty node. <\/p>\n\n\n\n<h3 class=\"wp-block-heading\">1. Adding nodes<\/h3>\n\n\n\n<p>Let&#8217;s add some data to this node.<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\nllist.head = Node(1)\n<\/pre><\/div>\n\n\n<p>Create a few other nodes for the linked list. <\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: plain; title: ; notranslate\" title=\"\">\n s = Node(2)\n t = Node(3) \n<\/pre><\/div>\n\n\n<h3 class=\"wp-block-heading\">2. Create links between the nodes <\/h3>\n\n\n\n<p>Creating links between the individual nodes is the most important part of creating a linked list. <\/p>\n\n\n\n<p>You can create the links using :<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\nllist.head.next_node = s\ns.next_node = t\n<\/pre><\/div>\n\n\n<h3 class=\"wp-block-heading\">3. Print the nodes of the list<\/h3>\n\n\n\n<p>To verify whether the list was created successfully or not we can use the print function. <\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\nllist.printList()\n<\/pre><\/div>\n\n\n<p>Output:<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: plain; title: ; notranslate\" title=\"\">\n1  -&gt; 2  -&gt; 3 \n<\/pre><\/div>\n\n\n<h3 class=\"wp-block-heading\">4. Output the size of the list <\/h3>\n\n\n\n<p>To output the size of the list, call the size function we wrote above. <\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\n print(llist.size())\n<\/pre><\/div>\n\n\n<p>Output :<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: plain; title: ; notranslate\" title=\"\">\n3\n<\/pre><\/div>\n\n\n<h3 class=\"wp-block-heading\">5. Insert a new node<\/h3>\n\n\n\n<p>Let&#8217;s try inserting some data at the head of the linked list using the function above. <\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\nllist.insert_at_head(5)\n<\/pre><\/div>\n\n\n<p>We can print the list to verify.<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\nllist.printList()\n<\/pre><\/div>\n\n\n<p>Output :<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: plain; title: ; notranslate\" title=\"\">\n5  -&gt; 1  -&gt; 2  -&gt; 3\n<\/pre><\/div>\n\n\n<h3 class=\"wp-block-heading\">6. Get next node <\/h3>\n\n\n\n<p>To get the next node: <\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\nprint(llist.get_next_node(s))\n<\/pre><\/div>\n\n\n<p>Output:<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: plain; title: ; notranslate\" title=\"\">\n3\n<\/pre><\/div>\n\n\n<h2 class=\"wp-block-heading\">Complete Implementation of Linked Lists in Python<\/h2>\n\n\n\n<p>The complete implementation is given below :<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\nclass Node(object):\n\n    def __init__(self, data=None, next_node=None):\n        self.data = data\n        self.next_node = next_node\n\n\nclass LinkedList(object):\n    def __init__(self, head=None):\n        self.head = head\n\n    def size(self):\n     current = self.head\n     count = 0\n     while current:\n        count += 1\n        current = current.next_node\n     return count\n      \n    def printList(self): \n        temp = self.head \n        while (temp): \n            print (temp.data, &quot; -&gt; &quot;, end = &#039;&#039;) \n            temp = temp.next_node\n        print(&quot;&quot;)\n\n    def insert_at_head(self, data):\n      new_node = Node(data)\n      new_node.next_node = self.head\n      self.head = new_node\n\n    def get_next_node (self,node):\n      return node.next_node.data\n\n\nif __name__==&#039;__main__&#039;: \n  \n    \n    llist = LinkedList() \n  \n    llist.head = Node(1) \n    s = Node(2) \n    t = Node(3) \n    llist.head.next_node = s;\n    s.next_node = t\n    llist.printList()\n    print(s.data)\n    print(llist.size())\n    print(llist.get_next_node(s))\n    llist.insert_at_head(5)\n    llist.printList()\n<\/pre><\/div>\n\n\n<h2 class=\"wp-block-heading\">Conclusion <\/h2>\n\n\n\n<p>This tutorial covered the implementation of linked lists in Python. We created our own linked list from scratch and wrote some additional functions to print the list, get the size of the list and make insertions at the head. <\/p>\n","protected":false},"excerpt":{"rendered":"<p>Linked lists in Python are one of the most interesting abstract data types that have continued to stay in popularity since the C\/C++ days. In this article, we&#8217;ll learn how to implement a Linked list in Python from scratch. What is a Linked List? A linked list is a linear data structure where each element [&hellip;]<\/p>\n","protected":false},"author":14,"featured_media":9367,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9],"tags":[],"class_list":["post-9366","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-examples"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/posts\/9366","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/users\/14"}],"replies":[{"embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/comments?post=9366"}],"version-history":[{"count":0,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/posts\/9366\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/media\/9367"}],"wp:attachment":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/media?parent=9366"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/categories?post=9366"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/tags?post=9366"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}