Python Linked Lists

A Linked List is, as the word implies, a list where the nodes are linked together. Each node contains data and a pointer. The way they are linked together is that each node points to where in the memory the next node is placed.

இணைக்கப்பட்ட பட்டியல் என்பது, அந்த வார்த்தை குறிப்பிடுவது போல, முனைகள் ஒன்றாக இணைக்கப்பட்டுள்ள ஒரு பட்டியல். ஒவ்வொரு முனையிலும் தரவு மற்றும் ஒரு சுட்டிக்காட்டி உள்ளது. அவை ஒன்றாக இணைக்கப்பட்டுள்ள விதம் என்னவென்றால், ஒவ்வொரு முனையும் நினைவகத்தில் அடுத்த முனை எங்கு வைக்கப்பட்டுள்ளது என்பதைக் குறிக்கிறது.

 

Linked Lists

A linked list consists of nodes with data, and a pointer, or link, to the next node.

இணைக்கப்பட்ட பட்டியலில் தரவுகளுடன் கூடிய முனைகளும், அடுத்த முனைக்கான ஒரு சுட்டிக்காட்டி அல்லது இணைப்பும் இருக்கும்.

Types of Linked Lists

• Singly linked lists
• Doubly linked lists
• Circular linked lists

 

இணைக்கப்பட்ட பட்டியல்களின் வகைகள்

• ஒற்றை இணைக்கப்பட்ட பட்டியல்கள்
• இரட்டை இணைக்கப்பட்ட பட்டியல்கள்
• வட்ட இணைக்கப்பட்ட பட்டியல்கள்

 

Singly linked lists / ஒற்றை இணைக்கப்பட்ட பட்டியல்கள்

A singly linked list is the simplest kind of linked lists. It takes up less space in memory because each node has only one address to the next node

ஒவ்வொரு முனையும் அடுத்த முனைக்கு ஒரே ஒரு முகவரியை மட்டுமே கொண்டிருப்பதால், இது நினைவகத்தில் குறைந்த இடத்தை எடுத்துக்கொள்கிறது.

Doubly linked lists /இரட்டை இணைக்கப்பட்ட பட்டியல்கள்

A doubly linked list has nodes with addresses to both the previous and the next node, it takes up more memory. But doubly linked lists are good if you want to be able to move both up and down in the list.

இரட்டை இணைக்கப்பட்ட பட்டியலில் முந்தைய மற்றும் அடுத்த முனைகளுக்கான முகவரிகள் கொண்ட முனைகள் உள்ளன, இது அதிக நினைவகத்தை எடுக்கும். ஆனால் பட்டியலில் மேலும் கீழும் நகர்த்த விரும்பினால் இரட்டை இணைக்கப்பட்ட பட்டியல்கள் நல்லது.

 

 

Circular linked lists / வட்ட இணைக்கப்பட்ட பட்டியல்கள்

A circular linked list is like a singly or doubly linked list with the first node, the “head”, and the last node, the “tail”, connected.

In singly or doubly linked lists, we can find the start and end of a list by just checking if the links are null. But for circular linked lists, more complex code is needed to explicitly check for start and end nodes in certain applications.

Circular linked lists are good for lists you need to cycle through continuously.

ஒரு வட்ட இணைக்கப்பட்ட பட்டியல் என்பது முதல் முனை, “தலை” மற்றும் கடைசி முனை, “வால்” இணைக்கப்பட்ட ஒற்றை அல்லது இரட்டை இணைக்கப்பட்ட பட்டியலைப் போன்றது.

 

ஒற்றை அல்லது இரட்டை இணைக்கப்பட்ட பட்டியல்களில், இணைப்புகள் பூஜ்யமாக உள்ளதா என்பதைச் சரிபார்ப்பதன் மூலம் பட்டியலின் தொடக்கத்தையும் முடிவையும் நாம் காணலாம். ஆனால் வட்ட இணைக்கப்பட்ட பட்டியல்களுக்கு, சில பயன்பாடுகளில் தொடக்க மற்றும் முடிவு முனைகளை வெளிப்படையாகச் சரிபார்க்க மிகவும் சிக்கலான குறியீடு தேவைப்படுகிறது.

 

நீங்கள் தொடர்ந்து சுழற்சி செய்ய வேண்டிய பட்டியல்களுக்கு வட்ட இணைக்கப்பட்ட பட்டியல்கள் நல்லது.

Singly circular

 

doubly circular

 

Linked List Operations / இணைக்கப்பட்ட பட்டியல் செயல்பாடுகள்

• Traversal / கடந்து செல்
• Remove a node / ஒரு முனையை அகற்ற
• Insert a node / ஒரு முனையைச் சேர்க்க
• Sort / வரிசைப்படுத்து

Traversal of a Linked List / இணைக்கப்பட்ட பட்டியலின் கடந்து செல்

Traversing a linked list means to go through the linked list by following the links from one node to the next.

Traversal of linked lists is typically done to search for a specific node, and read or modify the node’s content, remove the node, or insert a node right before or after that node.

To traverse a singly linked list, we start with the first node in the list, the head node, and follow that node’s next link, and the next node’s next link and so on, until the next address is null.

இணைக்கப்பட்ட பட்டியலைக் கடந்து செல்வது என்பது ஒரு முனையிலிருந்து அடுத்த முனைக்கு இணைப்புகளைப் பின்பற்றுவதன் மூலம் இணைக்கப்பட்ட பட்டியலைச் சுற்றிச் செல்வதாகும்.

இணைக்கப்பட்ட பட்டியல்களின் வழியாகச் செல்வது பொதுவாக ஒரு குறிப்பிட்ட முனையைத் தேடுவதற்கும், முனையின் உள்ளடக்கத்தைப் படிப்பதற்கும் அல்லது மாற்றுவதற்கும், முனையை அகற்றுவதற்கும் அல்லது அந்த முனைக்கு முன் அல்லது பின் ஒரு முனையைச் செருகுவதற்கும் செய்யப்படுகிறது.

தனித்தனியாக இணைக்கப்பட்ட பட்டியலைக் கடந்து செல்ல, பட்டியலில் உள்ள முதல் முனை, ஹெட் முனையுடன் தொடங்கி, அந்த முனையின் அடுத்த இணைப்பையும், அடுத்த முனையின் அடுத்த இணைப்பையும் பின்தொடர்ந்து, அடுத்த முகவரி முடியும்  வரை தொடர வேண்டும்.

 

Example / உதாரணம்

class Node:

def init(self, data):

self.data = data

self.next = None

 

def traverseAndPrint(head):

currentNode = head

while currentNode:

print(currentNode.data, end=” -> “)

currentNode = currentNode.next

print(“null”)

 

node1 = Node(“Vada”)

node2 = Node(“Idly”)

node3 = Node(“Sambar”)

node4 = Node(“Chuttney”)

node5 = Node(“Kesari”)

 

node1.next = node2

node2.next = node3

node3.next = node4

node4.next = node5

 

traverseAndPrint(node1)

 

Output:

Vada -> Idly -> Sambar -> Chuttney -> Kesari -> null

Delete a Node in a Linked List / இணைக்கப்பட்ட பட்டியலில் ஒரு முனையை நீக்குதல்

If you want to delete a node in a linked list, it is important to connect the nodes on each side of the node before deleting it, so that the linked list is not broken.

So before deleting the node, we need to get the next pointer from the previous node, and connect the previous node to the new next node before deleting the node in between.

Also, it is a good idea to first connect next pointer to the node after the node we want to delete, before we delete it. This is to avoid a ‘dangling’ pointer, a pointer that points to nothing, even if it is just for a brief moment.

The simulation below shows the node we want to delete, and how the list must be traversed first to connect the list properly before deleting the node without breaking the linked list.

 

இணைக்கப்பட்ட பட்டியலில் உள்ள ஒரு முனையை நீக்க விரும்பினால், அதை நீக்குவதற்கு முன் முனையின் ஒவ்வொரு பக்கத்திலும் உள்ள முனைகளை இணைப்பது முக்கியம், இதனால் இணைக்கப்பட்ட பட்டியல் உடைக்கப்படாது.

எனவே முனையை நீக்குவதற்கு முன், முந்தைய முனையிலிருந்து அடுத்த சுட்டிக்காட்டியைப் பெற வேண்டும், மேலும் இடையில் உள்ள முனையை நீக்குவதற்கு முன் முந்தைய முனையை புதிய அடுத்த முனையுடன் இணைக்க வேண்டும்.

 

மேலும், அதை நீக்குவதற்கு முன், நாம் நீக்க விரும்பும் முனைக்குப் பிறகு அடுத்த சுட்டிக்காட்டியை முனையுடன் இணைப்பது நல்லது. இது ஒரு ‘தொங்கும்’ சுட்டிக்காட்டியைத் தவிர்ப்பதற்காக, எதையும் சுட்டிக்காட்டாத ஒரு சுட்டிக்காட்டி, அது ஒரு குறுகிய தருணமாக இருந்தாலும் கூட.

 

கீழே உள்ள உருவகப்படுத்துதல், நாம் நீக்க விரும்பும் முனையையும், இணைக்கப்பட்ட பட்டியலை உடைக்காமல் முனையை நீக்குவதற்கு முன் பட்டியலை சரியாக இணைக்க முதலில் பட்டியலை எவ்வாறு கடக்க வேண்டும் என்பதையும் காட்டுகிறது.

 

Example / உதாரணம்

class Node:

def init(self, data):

self.data = data

self.next = None

 

def traverseAndPrint(head):

currentNode = head

while currentNode:

print(currentNode.data, end=” -> “)

currentNode = currentNode.next

print(“null”)

 

def deleteSpecificNode(head, nodeToDelete):

if head == nodeToDelete:

return head.next

 

currentNode = head

while currentNode.next and currentNode.next != nodeToDelete:

currentNode = currentNode.next

 

if currentNode.next is None:

return head

 

currentNode.next = currentNode.next.next

 

return head

 

node1 = Node(“Idly”)

node2 = Node(“Sambar”)

node3 = Node(“Chuttney”)

node4 = Node(“Kesari”)

 

 

node1.next = node2

node2.next = node3

node3.next = node4

 

 

print(“Before deletion:”)

traverseAndPrint(node1)

 

Delete node3

node1 = deleteSpecificNode(node1, node3)

 

print(“\nAfter deletion:”)

traverseAndPrint(node1)

Output:

Before deletion:

Idly -> Sambar -> Chuttney -> Kesari -> null

 

After deletion:

Idly -> Sambar -> Kesari -> null

 

 

Insert a Node in a Linked List / இணைக்கப்பட்ட பட்டியலில் ஒரு முனையைச் சேர்க்கவும்.

Inserting a node into a linked list is very similar to deleting a node, because in both cases we need to take care of the next pointers to make sure we do not break the linked list.

To insert a node in a linked list we first need to create the node, and then at the position where we insert it, we need to adjust the pointers so that the previous node points to the new node, and the new node points to the correct next node.

The simulation below shows how the links are adjusted when inserting a new node.

இணைக்கப்பட்ட பட்டியலில் ஒரு முனையைச் செருகுவது ஒரு முனையை நீக்குவதற்கு மிகவும் ஒத்ததாகும், ஏனெனில் இரண்டு சந்தர்ப்பங்களிலும் இணைக்கப்பட்ட பட்டியலை உடைக்காமல் இருக்க அடுத்த சுட்டிகளை நாம் கவனித்துக் கொள்ள வேண்டும்.

 

இணைக்கப்பட்ட பட்டியலில் ஒரு முனையைச் செருக, முதலில் முனையை உருவாக்க வேண்டும், பின்னர் அதைச் செருகும் நிலையில், முந்தைய முனை புதிய முனையையும், புதிய முனை சரியான அடுத்த முனையையும் சுட்டிக்காட்டும் வகையில் சுட்டிகளை சரிசெய்ய வேண்டும்.

கீழே உள்ள உருவகப்படுத்துதல் ஒரு புதிய முனையைச் சேர்க்கும்போது இணைப்புகள் எவ்வாறு சரிசெய்யப்படுகின்றன என்பதைக் காட்டுகிறது

 

New node is created

Node Dosai is linked to new node

New node is linked to next node

புதிய முனை உருவாக்கப்பட்டது

முனை தோசை புதிய முனையுடன் இணைக்கப்பட்டுள்ளது

புதிய முனை அடுத்த முனையுடன் இணைக்கப்பட்டுள்ளது

Example / உதாரணம்

class Node:

def init(self, data):

self.data = data

self.next = None

 

def traverseAndPrint(head):

currentNode = head

while currentNode:

print(currentNode.data, end=” -> “)

currentNode = currentNode.next

print(“null”)

 

def insertNodeAtPosition(head, newNode, position):

if position == 1:

newNode.next = head

return newNode

 

currentNode = head

for _ in range(position – 2):

if currentNode is None:

break

currentNode = currentNode.next

 

newNode.next = currentNode.next

currentNode.next = newNode

return head

 

node1 = Node(“Idly”)

node2 = Node(“Sambar”)

node3 = Node(“Chuttney”)

node4 = Node(“Kesari”)

 

 

node1.next = node2

node2.next = node3

node3.next = node4

 

print(“Original list:”)

traverseAndPrint(node1)

 

Insert a new node with value Dosai at position 4

newNode = Node(“Dosai”)

node1 = insertNodeAtPosition(node1, newNode, 4)

 

print(“\nAfter insertion:”)

traverseAndPrint(node1)

 

Output:

Original list:

Idly -> Sambar -> Chuttney -> Kesari -> null

After insertion:

Idly -> Sambar -> Chuttney -> Dosai -> Kesari -> null

 

Time Complexity of Linked Lists Operations / இணைக்கப்பட்ட பட்டியல் செயல்பாடுகளின் நேர தன்மை

Remember that time complexity just says something about the approximate number of operations needed by the algorithm based on a large set of data (n), and does not tell us the exact time a specific implementation of an algorithm takes.

ஒரு பெரிய தரவுத் தொகுப்பை (n) அடிப்படையாகக் கொண்ட வழிமுறைக்குத் தேவையான செயல்பாடுகளின் தோராயமான எண்ணிக்கையைப் பற்றி  ஏதோ சொல்கிறது என்பதை நினைவில் கொள்ளுங்கள், மேலும் ஒரு வழிமுறையின் குறிப்பிட்ட செயல்படுத்தல் எடுக்கும் சரியான நேரத்தை நமக்குத் தெரிவிக்காது.

 

This means that even though linear search is said to have the same time complexity for arrays as for linked list: O(n), it does not mean they take the same amount of time. The exact time it takes for an algorithm to run depends on programming language, computer hardware, differences in time needed for operations on arrays vs linked lists, and many other things as well.

அதாவது, நேரியல் தேடல் இணைக்கப்பட்ட பட்டியல் O(n) க்கு அணிவரிசைகளுக்கு அதே நேர தன்மையைக் கொண்டிருப்பதாகக் கூறப்பட்டாலும், அவை அதே அளவு நேரத்தை எடுத்துக்கொள்கின்றன என்று அர்த்தமல்ல. ஒரு வழிமுறை இயங்குவதற்கு எடுக்கும் சரியான நேரம் நிரலாக்க மொழி, கணினி வன்பொருள், வரிசைகள் vs இணைக்கப்பட்ட பட்டியல்களில் செயல்பாடுகளுக்குத் தேவையான நேர வேறுபாடுகள் மற்றும் பல விஷயங்களையும் சார்ந்துள்ளது.

Linear search for linked lists works the same as for arrays. A list of unsorted values are traversed from the head node until the node with the specific value is found. Time complexity is O(n).

இணைக்கப்பட்ட பட்டியல்களுக்கான நேரியல் தேடல் வரிசைகளைப் போலவே செயல்படுகிறது. குறிப்பிட்ட மதிப்புடன் கூடிய முனை கண்டுபிடிக்கப்படும் வரை வரிசைப்படுத்தப்படாத மதிப்புகளின் பட்டியல் தலை முனையிலிருந்து கடந்து செல்கிறது. நேர  O(n) ஆகும்.

Binary search is not possible for linked lists because the algorithm is based on jumping directly to different array elements, and that is not possible with linked lists.

இணைக்கப்பட்ட பட்டியல்களுக்கு பைனரி தேடல் சாத்தியமில்லை, ஏனெனில் வழிமுறை வெவ்வேறு வரிசை கூறுகளுக்கு நேரடியாகத் தாவுவதை அடிப்படையாகக் கொண்டது, மேலும் அது இணைக்கப்பட்ட பட்டியல்களுடன் சாத்தியமில்லை.

 

Sorting algorithms have the same time complexities as for arrays, and these are explained earlier in this tutorial. But remember, sorting algorithms that are based on directly accessing an array element based on an index, do not work on linked lists.

வரிசைப்படுத்தல் வழிமுறைகள் வரிசைகளுக்கு அதே நேர சிக்கல்களைக் கொண்டுள்ளன, மேலும் இவை இந்த பதிவில் முன்னர் விளக்கப்பட்டுள்ளன. ஆனால் நினைவில் கொள்ளுங்கள், ஒரு குறியீட்டின் அடிப்படையில் ஒரு வரிசை உறுப்பை நேரடியாக அணுகுவதன் அடிப்படையில் வரிசைப்படுத்தும் வழிமுறைகள், இணைக்கப்பட்ட பட்டியல்களில் வேலை செய்யாது.