In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. see wikipedia.org.
In this tutorial I will show you how these linked list works and how can build with python programming language.Let's start with some basic elements:
- Linked List is a linear data structure;
- Linked List are not array;
- Linked List are not stored at a contiguous location because use pointes;
- Each element use a linked pointe;
- Linked List has a dynamic size;
- Linked List use operations like insertion and deletion for each element;
- The access to elements is sequentially;
- Using reference to pointer foe each element needs extra memory space and is not cache friendly;
The Linked List consists of at least two parts: data and pointer to the next node.
The first element of the list is called the head.
The last node has a reference to null.
The each element named node of the list has a similar structure like Linked List: data node and pointer to the next node.
The data from Linked list is represent like a sequence.
A number of operations are required to use the Linked List.
The basic operations supported by a list can be:
- insertion - adds an element at the beginning of the list;
- deletion - deletes an element at the beginning of the list;
- display - displays the complete list;
- search - searches an element using the given key;
- delete - deletes an element using the given key.
The Advantages of Linked List elements can be easily inserted or removed without reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory or on disk using operations.
The Linked List structure allows several ways to link nodes resulting in a number of types of Linked List:- Simple linked list;
- Doubly linked list;
- Multiply linked list;
- Circular linked list;
- Sentinel nodes;
- Empty lists;
- Hash linking;
- List handles;
- Combining alternatives;
Let's start with first source code for the first type of Linked List named Simple linked list.
Python 3.8.5 (default, Aug 12 2020, 00:00:00)
[GCC 10.2.1 20200723 (Red Hat 10.2.1-1)] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> # create a node class
>>> class Node:
... # first initialise of the node object
... def __init__(self, data):
... # assign the node data
... self.data = data
... # initialize next element as null
... self.next = None
...
>>> # create a simple linked list
>>> class Simple_LinkedList:
... # first initialize of element named head
... def __init__(self):
... self.head = None
>>> # use the list
>>> if __name__=='__main__':
... simple_list = Simple_LinkedList()
... simple_list.head = Node(1)
... second = Node(2)
... third = Node(3)
... #link first node with the second
... simple_list.head.next = second
... #link second node with the third
... second.next = third
... # now the list is linked as a simple Linked ListThis source code don't include any basic operations.
If you put this source code into python script and run it you will see this:
[mythcat@desk ~]$ python simple_LinkedList.py
<__main__.Node object at 0x7f35163e1ac0>
<__main__.Node object at 0x7f351638b0a0>
<__main__.Node object at 0x7f351638b130>I create a basic operation for this simple Linked List to display the content of this list:
# create a simple linked list with a basic diplay operation
class Simple_LinkedList:
# first initialize of element named head
def __init__(self):
self.head = None
# use the basic operation for display
def display_Simple_LinkedList(self):
points_to_node = self.head
#will traverse the list to the last node.
while (points_to_node):
# print data linked to points_to_node
print (points_to_node.data)
# print next node linked to points_to_node
points_to_node = points_to_node.nextI run with this new python source code and result is this:
[mythcat@desk ~]$ python simple_LinkedList_basic_display.py
1
2
3 
