Referene1
Referene2
Referene3
Referene4
php-linked-list
php-linked-list
Linked List in Data Structure
There are broadly two types of Data structures: Linear and Non-linear. Linear data structures are those in which every element is connected to the previous element and the elements are present at a single level.
Some examples of linear data structures are- Arrays, linked lists, stack,s and queues. Thus, a linked list is a linear data structure in which elements are not stored contiguously in the memory.
Let’s learn about Linked List in Data Structure.
What is a Linked list?
A linked list a collection of randomly stored elements in the memory. These elements are called nodes.
We use pointers to connect and maintain the linear order between these random data points.
Every node of a linked list consists of at least two parts-
Data
Address of next node(pointers)
Representation of Linked List
Let's see how each node of the linked list is represented. Each node consists:
A data item
An address of another node
We wrap both the data item and the next node reference in a struct as:
struct node
{
int data;
struct node *next;
};
Understanding the structure of a linked list node is the key to having a grasp on it.
Each struct node has a data item and a pointer to another struct node. Let us create a simple Linked List with three items to understand how this works.
/* Initialize nodes */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;
/* Allocate memory */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));
/* Assign data values */
one->data = 1;
two->data = 2;
three->data=3;
/* Connect nodes */
one->next = two;
two->next = three;
three->next = NULL;
/* Save address of first node in head */
head = one;
If you didn't understand any of the lines above, all you need is a refresher on pointers and structs.
In just a few steps, we have created a simple linked list with three nodes.
The above diagram shows that in a linked list, the elements are not stored contiguously but it appears that they are stored contiguously.
The most important thing in a linked list is the pointer. We need to have a starting pointer (HEAD) to access the linked list. The last node in the linked list has a pointer to NULL.
Properties of linked list in Data Structure
The elements of the linked list may or may not be present contiguously in the memory.
We need not declare the list size in advance.
We can allocate the memory dynamically whenever we need to add more nodes or perform any other operation on the list.
The linked list cannot contain an empty node.
A node in a linked list is a combination of two data types- a pointer and a primitive data type such as int or float. Therefore, we use structures to implement a linked list.
Applications of Linked List in Data Structure
We can implement stack and queue data structures using a linked list.
It is used in the implementation of graphs. Example- Adjacency list representation in a graph makes use of a linked list.
Symbol table management in compiler design uses a linked list.
It is used to prevent collision in hashing.
Linked list is used for DMA (Dynamic Memory Allocation).
We can use linked lists for performing arithmetic operations on long int.
Representation of a sparse tree matrix also requires a linked list.
Data Structure Linked List vs Array
Both arrays and linked lists have their own use cases, advantages as well as disadvantages.
Let us see a few comparisons between them.
Basic Operations on Linked List
There are certain basic operations that a linked list data structure supports. These operations are:
Traversal:
It means visiting each node from the beginning till the end.Insertion:
This operation inserts an element at any given position in the list.Deletion:
Deletion operation helps in deleting a node from the linked list.Display:
This operation is used to print/display all the data elements of the linked list.Search:
search operation helps in searching an element by traversing it.
Declaration and Initialization of a Node in a linked list:
A node is a heterogeneous data type. Therefore, we use a structure to create it.
struct Node
{
int data; //the first part of the node where data is stored
struct node *Next; //Self-referencing structure. It links two nodes.
};
The linked list supports dynamic memory allocation. Therefore, we will use the functions malloc, calloc and realloc for memory allocation.
The code will be:
struct Node *Head, *Ptr; //Declaring two pointers- Head and Ptr
Ptr = (struct Node *)malloc(sizeof(struct Node *)); //Initializing Ptr
Dynamic memory is allocated inside the heap, which is why we need functions like malloc. Here, malloc will return the address of the node.
Traversal in a Singly Linked List
Traversal means visiting each node of the linked list. Once the node has been created, we can do its traversal in the following way.
struct Node *Ptr;
Ptr = Head;
while(Ptr != NULL)
{
Print (Ptr→data);
Ptr = Ptr→Next;
}
The time complexity for the above pseudo-code will be O(n).
Insertion in a Linked List
When we talk about insertion in a linked list, we take into consideration three different cases:
Insertion at the beginning of the list
Insertion after a particular node.
Insertion at the end of the list
Insertion at the beginning:
Insertion at the beginning means we will insert a node at the front of the list in the following way:
The above diagram shows that we have a linked list of the following elements: 10→20→30.
Once we insert a new node at the beginning, the list will be 50→10→20→30.
Pseudo-code:
Void Insert_at_beginning(int key)
{
struct Node *temp; //temp is a pointer pointing to the node to be inserted.
temp = (struct Node*) malloc(sizeof(struct Node));
if(temp != NULL)
{
temp→data = key; //key is the data value to be inserted
temp→next = Head; //this step will make the incoming node the first node.
}
}
Insertion after a particular node
We need to traverse all the nodes before the position of insertion of the new node. For doing this, we maintain an additional temporary pointer.
For example, suppose we wish to link all the letters of the word ‘TECHVIDVAN’ and we forgot to add “H”.
We can insert this ‘H’ once the list is created as shown below
In this case, we will have a temporary pointer named ‘temp’. This pointer temp will be pointing to ‘C’ because we need to insert ‘H’ after ‘C’.
The lines of code that will help to do this will be:
temp->Next = Ptr->Next;
Ptr->Next = temp;
Insertion at the End:
To insert a node at the end of the list, we first need to traverse the whole list.
The function for insertion at the end is:
void Insert_at_end(int key)
{
struct Node *temp, *Ptr;
temp = (struct Node*) malloc(sizeof(struct Node));
if(temp != NULL)
{
temp->data = key;
temp->Next = NULL;
if(Head == NULL) //This will be true if the list is initially empty
{
Head = temp;
return;
}
Ptr = Head;
while(Ptr->Next != NULL)
Ptr->Next = temp;
}
}
Deletion from a Linked List:
Just like insertion, deletion also works in three different cases:
Deletion from beginning
Deletion at the end
Deleting a node other than the first and the last node
Deletion from the beginning:
It involves deleting the first node of the linked list.
Suppose we initially had the linked list elements as 10→20→30→40.
If we perform deletion of one node at the beginning, the linked list will be:
20→30→40.
The function for performing deletion at the beginning is:
void Delete_from_beginning(int key)
{
struct Node *Ptr = Head;
if(Head == NULL) //i.e. If the list is empty
{
return;
}
Head = Head->Next; //linking Head with the 2nd node of the list
free(Ptr);
}
Whenever we delete a node, we make the memory area occupied by that node free by using the ‘free’ function. Otherwise, it might lead to a memory leakage problem.
Deletion at the end:
For deletion of the last node, we need to make the address of the second last node point to NULL. For doing this, we will make use of an extra pointer named ‘Prev’.
While deleting the last node, we will first free the last node and then make the Next of the second last node as NULL.
The function for deletion at the end will as follows:
void Delete_at_end(int key)
{
struct Node *Ptr = Head;
struct Node *Prev = NULL;
if(Head == NULL) //If the list is empty
{
return;
}
if(Head->Next == NULL) //If the list has only one element
{
Head = NULL;
free(Ptr);
}
else
{
while(Ptr->Next != NULL)
{
Prev = Ptr;
Ptr = Ptr->Next;
}
free(Ptr);
}
}
Deletion after a particular node:
If we have the address of a particular node, we can always delete the node next to it.
Let us consider a linked list: 10→20→30→40.
Suppose we wish to delete 20 from it, we will delete the node containing 30 and then rewrite the value of 20 as 30.
The lines of code for doing this will be:
Ptr->data = Ptr->Next->data;
Ptr = Ptr->Next;
Ptr->Next = Ptr->Next->Next;
free(Ptr);
Thus, after deleting 20, the new list will be 10→30→40.
Reversing a linked list:
To reverse a linked list, we need to reverse the pointers.
For example, if the list is 10→20→30→40,
On reversing we will have 10←20←30←40 and 10 will point to NULL.
The recursive approach to reverse a list is as follows:
int Reverse_list(struct Node *Head)
{
struct Node *remaining;
if (Head == NULL || Head->Next == NULL)
return Head;
Node* remaining = Reverse_list(Head->Next);
Head->Next->Next = Head;
Head->Next = NULL;
return remaining;
}
Uses of Linked List
The size of the linked list is limited to the memory size due to dynamic memory allocation. That is why, we need not declare the size of the list beforehand, rather we can do that at run time.
A linked list can never contain an empty node.
Although a linked list is a linear data structure, it is unnecessary to store it contiguously in the memory. This is because the list is connected through addresses/pointers. This helps in the efficient utilization of memory space.
Linked List Implementations in Java
// Linked list implementation in Java
class LinkedList {
// Creating a node
Node head;
static class Node {
int value;
Node next;
Node(int d) {
value = d;
next = null;
}
}
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
// Assign value values
linkedList.head = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
// Connect nodess
linkedList.head.next = second;
second.next = third;
// printing node-value
while (linkedList.head != null) {
System.out.print(linkedList.head.value + " ");
linkedList.head = linkedList.head.next;
}
}
}
import java.io.*;
// Java program to implement
// a Singly Linked List
public class LinkedList {
Node head; // head of list
// Linked list Node.
// This inner class is made static
// so that main() can access it
static class Node {
int data;
Node next;
// Constructor
Node(int d)
{
data = d;
next = null;
}
}
// Method to insert a new node
public static LinkedList insert(LinkedList list, int data)
{
// Create a new node with given data
Node new_node = new Node(data);
new_node.next = null;
// If the Linked List is empty,
// then make the new node as head
if (list.head == null) {
list.head = new_node;
}
else {
// Else traverse till the last node
// and insert the new_node there
Node last = list.head;
while (last.next != null) {
last = last.next;
}
// Insert the new_node at last node
last.next = new_node;
}
// Return the list by head
return list;
}
// Method to print the LinkedList.
public static void printList(LinkedList list)
{
Node currNode = list.head;
System.out.print("LinkedList: ");
// Traverse through the LinkedList
while (currNode != null) {
// Print the data at current node
System.out.print(currNode.data + " ");
// Go to next node
currNode = currNode.next;
}
}
// Driver code
public static void main(String[] args)
{
/* Start with the empty list. */
LinkedList list = new LinkedList();
//
// ******INSERTION******
//
// Insert the values
list = insert(list, 1);
list = insert(list, 2);
list = insert(list, 3);
list = insert(list, 4);
list = insert(list, 5);
list = insert(list, 6);
list = insert(list, 7);
list = insert(list, 8);
// Print the LinkedList
printList(list);
}
}
}
Linked list implementation in Python
class Node:
# Creating a node
def __init__(self, item):
self.item = item
self.next = None
class LinkedList:
def __init__(self):
self.head = None
if __name__ == '__main__':
linked_list = LinkedList()
# Assign item values
linked_list.head = Node(1)
second = Node(2)
third = Node(3)
# Connect nodes
linked_list.head.next = second
second.next = third
# Print the linked list item
while linked_list.head != None:
print(linked_list.head.item, end=" ")
linked_list.head = linked_list.head.next
Linked list implementation in php
php-linked-list
php-linked-list
First, you need to define a Node class that represents a single node in the linked list.
This class will have two properties: $data which will store the data element of the node, and $next which will store a reference to the next node in the sequence.
class Node {
// data stored in this node
public $data;
// reference to the next node
public $next;
// initialize the node with the given data
function __construct($data) {
$this->data = $data;
$this->next = null;
}
}
Next, define a SinglyLinkedList class that represents the linked list itself.
This class will have a $head property that stores a reference to the first node in the list, and a $tail property that stores a reference to the last node in the list.
class SinglyLinkedList {
// head of the linked list
public $head;
// tail of the linked list
public $tail;
// initialize the linked list
function __construct() {
$this->head = null;
$this->tail = null;
}
}
<?php
class Node{
public $data;
public $next;
public $visited;
public function __construct($data){
$this->data = $data;
$this->next = null;
$this->visited = false;
}
}
class LinkedList
{
public $headNode = null;
public $count = 0;
public function insert($data)
{
//create a new node object with the data we want to insert. Takes O(n) time.
$newNode = new Node($data);
//head node 'null' indicates there is no node in the list
if ($this->headNode == null) {
//make the newnode as the head node
$this->headNode = $newNode;
} else {
//else traverse throught last position and insert the new node at the last position
$current = $this->headNode;
while ($current->next != null) {
$current = $current->next;
}
//now 'current' next filed points to the new node we created
$current->next = $newNode;
}
$this->display();
//increment the count indicating one node is entered in the list.
$this->count++;
}
//takes O(1) time
public function insertAtFront($data)
{
$newNode = new Node($data);
if ($this->headNode == null) {
$this->headNode = $newNode;
} else {
//store the current head node in a variable.
$currenthead = $this->headNode;
//make the new node we want to insert as the head node.
$this->headNode = $newNode;
//make the new node next field point to the previous head node that is in 'currentHead' variable
$newNode->next = $currenthead;
}
$this->display();
$this->count++;
}
//takes O(n) time
public function insertAtPosition($data, $position)
{
$newNode = new Node($data);
//if the position is zero call the insertAtFront method, position zero indicates that we want ot insert the node at the front of the list
if ($position == 0) {
$this->insertAtFront($data);
} else {
$current = $this->headNode;
//traverse the node until we reach the position
for ($i = 1; $i < $position; $i++) {
$current = $current->next;
}
//now the current node contains the node we want to insert at the given position.
//make the new node's next field to point to the 'current' node's next node.
$newNode->next = $current->next;
//make the 'current' node next field to point to the new node
$current->next = $newNode;
}
$this->display();
$this->count++;
}
//takes O(n) time
public function display(){
$current = $this->headNode;
//traverse the list
while($current != null){
//while traversing print the data field of the current node we are traversing
echo $current->data ,"->";
$current = $current->next;
}
//not compulsory..to just indicate that we reach the end of the list
echo "NULL";
echo "\n";
}
//takes O(1) time
public function deleteFirst(){
//if the head node is null there is no element to be deleted...a simple check whether the head node is not null
if($this->headNode != null){
//checking if the head node's next field is not null..if it is null there is only head node is present in the list...'else' block covers this case
if($this->headNode->next != null){
$this->headNode = $this->headNode->next;
}
}else{
$this->headNode = null;
}
$this->display();
//decrement the count indicating a node is deleted from the list
$this->count--;
}
//takes O(n) time
public function deleteLast(){
if($this->headNode != null){
if($this->headNode->next == null){
$this->headNode =null;
}else{
//traverse until u reach the last position of the list
$current = $this->headNode;
while($current->next != null){
//keep track of the previous node while traversing
$prev = $current;
$current = $current->next;
}
//set the previous node's next to point null...thus the last node lose its reference
$prev->next = null;
}
}
$this->display();
$this->count--;
}
public function delete($data){
if($this->headNode != null){
//if the data is the 'headnode' call delete first method
if($this->headNode->data == $data){
$this->deleteFirst();
}
if($this->headNode->next != null){
$prev = null;
$current = $this->headNode;
//traverse the list
while($current->next != null){
//if the data matches the current node's data we are iterating..
if($current->data === $data){
//if we are at last..
if($current->next == null){
$prev->next = null;
}else{
// else point the previous node's next pointer to point to the current node we are iterating next node.
$prev->next = $current->next;
}
}
//keep track of the previous node while we are iterating
$prev = $current;
$current = $current->next;
}
}
$this->display();
$this->count--;
}
}
Insertion After target Node:
Insertion at begining:
deletion at first:
deletion at last:
deletion at given position:
Top comments (0)