Danh mụcThẻBài viết

admin

I'm a Full-stack developer

Thẻ

Linked List
Data Structure
Chat GPT
Design Pattern
Microservices
API
AWS CDK
ReactJS
AWS Lightsail
Flutter Mobile
Data structure: Singly Linked List
Ngày đăng: 07/04/2024

In a previous post, I introduced data structure including: What are data structures? Classification of data structure.

In this article, I will show you how to set up a singly linked list algorithm in Python.


Table of content

  • What is a Linked List data structure?
  • What is a Singly Linked List?
  • How to implement in Python
  • Setup
  • Insertion
  • Deletion
  • Conclusion


What is a Linked List data structure?

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.


What is a Singly Linked List?

A singly linked list is a linear data structure in which the elements are not stored in contiguous memory locations and each element is connected only to its next element using a pointer.


How to implement in Python

You can clone the source code here to follow it easier.

Setup

  • Create a new file.
mkdir singly_linked_list
cd singly_linked_list
vi singly_linked_list.py


  • Create a new class with the name Node
class Node:
  def __init__(self, data: int) -> None:
    self.data = data
    self.next = None


  • Create a new class SinglyLinkedList
class SinglyLinkedList:
  def __init__(self) -> None:
    self.head = None


Insertion

There are three types:


  • At the beginning
  • At the end
  • At a given position


Insert a node at the beginning

Step to insert:

  1. Create a new node, and the next pointer is the head node.
  2. Update head node and new node created.
def insert_at_head(self, data: int):
  new_node = Node(data)
  new_node.next = self.head
  self.head = new_node


Insert a node at the end


Step to insert:

  1. Create a new node, and the next pointer is None
  2. Update last node pointer is a new node created
def insert_at_tail(self, data: int):
  node_len = self.get_len()

  if (node_len == 0):
    return self.insert_at_head(data)

  new_node = Node(data)
  current = self.head

  while current.next:
    current = current.next
  current.next = new_node


Insert a node at a given position




Step to insert:

  1. Get an index of node B
  2. Create a new node, and the pointer is now node C
  3. Update node B pointer is a new node created
def insert_at_index(self, data: int, index: int):
  if (index < 0):
    return None
  
  if (index == 0):
    return self.insert_at_head(data)

  node_len = self.get_len()
  if (index >= node_len):
    return self.insert_at_tail(data)
  
  new_node = Node(data)
  prev_node = self.get_node_at_index(index - 1)
  new_node.next = prev_node.next
  prev_node.next = new_node


Deletion

There are three types:

  • At the begginning
  • At the end
  • At a given position


Delete a node at the beginning

Step to delete:

  1. Get the second node in the list
  2. Update head node is the second node
def delete_first_node(self):
  if (self.head is None):
    return None

  new_first_node = self.head.next
  self.head = new_first_node


Delete a node at the end


Step to delete:

  1. Get near the last node in the list
  2. Update next pointer this node is None
def delete_last_node(self):
  if (self.head is None or self.head.next is None):
    return self.delete_first_node()
  
  node_len = self.get_len()
  prev_node = self.get_node_at_index(node_len - 2)
  prev_node.next = None


Delete a node at a given position

Step to delete:

  1. Get the previous node, the next node, and the node that should be deleted
  2. Update the previous node pointer is the next node
def delete_node_at_index(self, index: int):
  if (self.head is None or index < 0):
    return None
  
  if (index == 0):
    return self.delete_first_node()
  
  if (index >= self.get_len() - 1):
    return self.delete_last_node()
  
  prev_node = self.get_node_at_index(index - 1)
  del_node = self.get_node_at_index(index)
  next_node = del_node.next

  prev_node.next = next_node


Conclusion

In this article, I introduced linked lists and the algorithm settings for a single-linked list in Python.

Hope this article will be useful to you.

My door is always open if you have any comments.


Continue, You want to be able to setup a doubly linked list in Python that I will show you in the next article Doubly linked list.


Document references:

  • https://www.geeksforgeeks.org/data-structures/linked-list/
  • https://viblo.asia/p/cau-truc-du-lieu-va-giai-thuat-danh-sach-lien-ket-don-singly-linked-list-naQZRk0Xlvx
Đề xuất

TypeScript Design Pattern - Adapter
admin08/08/2023

TypeScript Design Pattern - Adapter
This design pattern acts as a bridge between two different interfaces.
Data structure: Doubly Linked List
admin07/04/2024

Data structure: Doubly Linked List
In this article, I would like to show you about Data structure - Doubly Linked List
Part 2: The hooks are used popularly in React
admin18/06/2023

Part 2: The hooks are used popularly in React
As a newbie React developer, does not understand when is use stateless (functional) components or stateful components. React hook is a new feature from v16.8, the developer does not worry about react lifecycle, and it is difficult to learn for newbies.
Mới nhất

🚀 Using Bitwise Oprators to build a RBAC in Node.js 🚀
admin13/04/2024

🚀 Using Bitwise Oprators to build a RBAC in Node.js 🚀
In this article, I will illustrate to you how to build an RBAC in Node.js using Bitwise Operators.
TypeScript Design Pattern - Abstract Factory
admin07/08/2023

TypeScript Design Pattern - Abstract Factory
The abstract factory pattern is one of five design patterns in the Creational Design Pattern group. The abstract factory provides an interface for creating families of related or dependent objects without specifying their concrete classes.
Create Cognito User Pool with AWS CDK
admin09/06/2023

Create Cognito User Pool with AWS CDK
In the previous post, I showed you how to create a simple S3 bucket. Next, in this article, I will guide you to create a Cognito User Pool.
Đinh Thành Công Blog

My website, where I write blogs on a variety of topics and where I have some experiments with new technologies.

hotlinelinkedinskypezalofacebook
DMCA.com Protection Status
Góp ý
Họ & Tên
Số điện thoại
Email
Nội dung
Tải ứng dụng
hotline

copyright © 2023 - AGAPIFA

Privacy
Term
About