Singly linked list python

How to Implement a Linked List in Python

Exploring how to write Linked List and Node objects from scratch using Python

Introduction

Linked Lists are among the most fundamental data structure that represents a sequence of nodes. The first element of the sequence is called the head of the Linked List while the last element corresponds to the tail.

Every node in the sequence has a pointer to the next element and optionally a pointer to the previous element. In Singly Linked Lists each node points to only the next node.

On the other hand, in Doubly Linked Lists each node points to the next as well as to the previous node.

Linked Lists are extremely useful in various scenarios. They are typically preferred over standard arrays when

• you need a constant time when adding or removing elements from the sequence
• manage memory more efficiently especially when the number of elements is unknown (if arrays you may have to constantly shrink or grow them. Note though that filled arrays usually take up less memory than Linked Lists.
• you want to insert items in the middle point more efficiently

Unlike other general purpose languages, Python does not have a built-in implementation of Linked Lists in its standard library. In today’s article we will explore how to implement a user-defined Linked List class using Python.

Implementing User Defined Linked Link Class in Python

First, let’s create a user-defined class for individual nodes in a Linked List. This class will be suitable for both Singly or Doubly Linked Lists. Therefore, the instances of this class should be capable for storing the value of the node, the next as well as the previous node.

class Node: 
def __init__(self, value, next_node=None, prev_node=None): 
self.value = value 
self.next = next_node 
self.prev = prev_node
 
def __str__(self): 
return str(self.value)

Note that when an instance of a Node has next set to None then it means that it is essentially the tail of the Linked List (either Singly or Doubly). Similarly, in…

Источник

Data Structure — Single Linked List in Python

Below is a simple depiction of a single linked list:

Every linked list consists of nodes, we call the first node as ‘head’ and the last as ‘tail’, and for each node it has two components:

• data, it allows a node in the linked list to store an element of data that can be of type string, character, number, or any other type of object.
• next, it is a pointer that points from one node to another.

Sometimes, we may need a dummy head in the linked list that can help us with intrusion or deletion the first node.

2. Difference with Array

Insertion/ Deletion

• If we are given the exact pointer after which we have to insert another node or delete a node, it will be a constant-time operation.
• However, the insertion/deletion operation is in O(n) operations for insertion/deletion of value at the array. Due to the shifting of the elements, the time complexity is O(n) .

Accessing Elements

• Accessing an n-th element in a linked list is an O(n) operation given that you have access to the head node of the linked list.
• It is a constant time operation to access elements in arrays, if given an array and an index.

3. Implementation

1). General classes

Single linked lists contain two kinds of classes:

• Node class, Every node is going to consist of data and next .
• LinkedList class, except constructor, it initially contains print_list() methos to show each node’s data.

class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def print_list(self): """ it will print out the data of each node from head to tail. """ cur_node = self.head while cur_node: print(cur_node.data) cur_node = cur_node.next 

2). Insertion

Now we’ll insert elements in a linked list by different ways:

• append , the append method will insert an element at the end of the linked list. For append method, we should consider two kinds of situations:
  • if the linked list is empty, or
  • if the linked list is not empty.

  def append(self, data): """ the append method will insert an element at the end of the linked list. """ new_node = Node(data) # create a node that will be inserted if not self.head: # the linked list is empty self.head = new_node return last_node = self.head # the linked list is not empty while last_node.next: last_node = last_node.next last_node.next = new_node 

  def prepend(self, data): """ it will insert an element at the beginning of the linked list. """ new_node = Node(data) new_node.next = self.head self.head = new_node 

  • First of all, we will create a new node based on the given data;
  • Next, we need to check if the node to be inserted after is in the linked list or not(here just check whether it is a non-node);
  • Last, we change the next pointer of the previous node to point to the new node.

  def insert_after_node(self, pre_node, data): """ it will insert an element after a given node. """ if not pre_node: print("Previous node is None") return new_node = Node(data) new_node.next = pre_node.next pre_node.next = new_node 

  3). Deletion

  3-1). Deletion by Value

  To delete a node in the linked list, first is to find the node to be deleted by traversing the linked list first. Then, delete that node and update the rest of pointers. However, to solve this problem, we need to handle two cases:

  def delete_node(self, data): """ this method will delete the given data node if existed in the linked list """ cur_node = self.head if cur_node and cur_node.data == data: # deal with the case of head self.head = cur_node.next cur_node = None return else: pre_node = None # other cases while cur_node and cur_node.data != data: pre_node = cur_node cur_node = cur_node.next if not cur_node: return pre_node.next = cur_node.next cur_node = None 

  3-2). Deletion by position

  Now, let’s delete a node based on position rather than value. Again, we’ll consider the above twos cases

  def delete_node_at_pos(self, pos): """ it will delete a node based on given position. """ cur_node = self.head if cur_node and pos == 0: # deal with the case of head self.head = cur_node.next cur_node = None count = 0 # other cases pre_node = None while cur_node and count != pos: pre_node = cur_node cur_node = cur_node.next count += 1 if not cur_node: return pre_node.next = cur_node.next cur_node = None 

  4). Length

  There are two ways to calculate the number of nodes in a linked list, which are iterative and recursive manners.

  4-1). Iterative solution

  def len_iterative(self): """ return the number of nodes in a linked list, using iterative method """ count = 0; cur_node = self.head while cur_node: count += 1 cur_node = cur_node.next return count 

  4-2). Recursive solution

  Before we start the recursive solution, let’s look the following diagram that could help us understand the method more specific.

  

  For any recursive method, we need a base case. In this class, the base case is whether or not we’ve encountered the end of the linked list which means the None pointer.

  • if we reach the end of the linked list, it should return 0 , otherwise;
  • call the recursive method and pass in the next node and plus 1 .

  def len_recursive(self, node): """ return the number of nodes in a linked list, using recursive method """ if not node: return 0 # base case return 1 + self.len_recursive(node.next) 

  5). Node Swap

  Now, assume we have two keys corresponding to the data element in the nodes, we would like to swap the two nodes in a linked list, what should we do?

  One way to solve this is by iterating the linked list and keeping track of certain pieces of information that are going to be helpful.

  • We can start from the first node of the linked list and keep track of both the previous and the current node.
  • If the data element of the node that we’re on matches one of the two keys, we record the information and repeat the process for the second node

  There are two cases that we’ll have to cater for:

  def swap_nodes(self, data_1, data_2): """ it will swap two nodes if they're existed in the linked list """ if data_1 == data_2: return # two data are duplicate. pre_1, cur_1 = None, self.head # looking for the data_1 and its previus node while cur_1 and cur_1.data != data_1: pre_1 = cur_1 cur_1 = cur_1.next pre_2, cur_2 = None, self.head # looking for the data_2 and its previuos node while cur_2 and cur_2.data != data_2: pre_2 = cur_2 cur_2 = cur_2.next if not cur_1 or not cur_2: return #cur_1 or cur_2 is none, means one of the data is no existed in linked list if pre_1: pre_1.next = cur_2 else: # data_1 is the head node self.head = cur_2 if pre_2: pre_2.next = cur1 else: # data_2 is the head node self.head = cur_1 cur_2.next, cur_1.next = cur_1.next, cur_2.next # swap the two nodes. 

  6). Reverse

  In this part, let’s talk about how to reverse a singly linked list in an iterative way and a recursive way. Before getting started, let’s know how to reverse a linked list first.

  

  6-1). Iterative implementation

  The key idea is that we’re reversing the orientation of the arrows. For example, node A is initially pointing to node B but after we flip them, node B points to node A. The same is the case for other nodes.

  def reverse_itr(self): """ reverse the linked list, using iterative method """ pre, cur = None, self.head while cur: # three pointers for reversing nxt = cur.next; cur.next = prev prev = cur cur = nxt # new head after reversing self.head = prev 

  6-2). Recursive Implementation

  The crux of recursive solution is as follows:

  • the base case;
  • assume we solve the simplest problem, which in this case is to reverse just ONE pair of nodes
  • the rest nodes of the linked list will repeat above process.

  def reverse_rec(self): """ it will reverse the linked list, using recursive method """ def _reverse(pre, cur): if cur: _reverse(cur, cur.next) cur.next = pre else: self.head = pre _reverse_recursive(pre=None, cur=self.head) # setting the head, which is the pre 

  7). Remove Duplicates

  We can use a hash-table or dictionary in Python to remove duplicates from a linked list.

  • The general idea is to go through the linked list once and keep track of all the data held at each of the nodes.
  • Use a dictionary to keep track of the data elements that we encounter to determine whether in the dictionary.

  def remove_deuplicates(self): """ it will remove duplicate data held by nodes, using a dictionary. """ dup_data = dict() cur = self.head pre = None while cur: if cur.data in dup_data: # if the data has existed in the dictionary, then removing it pre.next = cur.next cur = None else: dup_data[cur.data] = 1 # else, put the data in the dictionary pre = cur cur = pre.next 

  8). Nth-from-last Nodes

  Now let’s dive into the solutions:

  1. ragualer way, counting the length, break down this solution in two simple steps:
     • Calculate the length of the linked list.
     • Count down from the total length until n is reached.

  Let’s look into the implementation:

  def print_nth_from_last(self, n): """ to find the data of n-th node from the last, using length of the linked list """ total_len = self.len_iterative() cur = self.head while cur: # countdown using total_len decrement if total_len == n: return cur.data total -= 1 cur = cur.next if not cur: print(str(n) + "is greater than the length of the linked list.") return 

  1. two pinters pattern, when fast pointer or next node of fast pointer is None, the slow pointer will reach the n
     • p will point to the head node.
     • q will point n nodes beyond head node.

  About two pointers pattern, the slow pointer will at the middle of the linked list, if the fast node is none or fast node’s next node is none. This because, in even length fast node will be the (length // 2 + 1) , in odd length the fast node will be the excat middle one.

  Here, this pattern can be used to look for the nth-node from the last node. The idea behind this solution is that the gap between p and q is the n, when p or q.next is None

  def print_nth_from_last(self, n): """ to find out the data of n-th node from the last, using two pointer pattern """ p = q = self.head count = 0 while q: # q points to the n-th node from the head count += 1 # count += 1, because q have pointed 1 node already. if count >= n: break q = q.next if not q: print(str(n) + "is greater than the length of the linked list.") while p and q.next: #gap between p and q is n, when p or q.next is None, the n-th node from last is found p = p.next q = q.next return p.data 

  Both the solutions have been made part of the LinkedList class. We can call the solution of the choice by passing in 1 or 2 as method to print_nth_from_last(self, n, method) .

  Originally published May 08, 2020
  Latest update May 09, 2020

  Related posts :

  Источник