DATA STRUCTURE AND ALGORITHM (Linked List)

-

 LINKED LIST


Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at a contiguous location; the elements are linked using pointers.


linkedlist

Why Linked List? 
Arrays can be used to store linear data of similar types, but arrays have the following limitations. 
1) The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage. 
2) Inserting a new element in an array of elements is expensive because the room has to be created for the new elements and to create room existing elements have to be shifted. 

Advantages over arrays 
1) Dynamic size 
2) Ease of insertion/deletion
Drawbacks: 
1) Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists efficiently with its default implementation.
2) Extra memory space for a pointer is required with each element of the list. 
3) Not cache friendly. Since array elements are contiguous locations, there is locality of reference which is not there in case of linked lists.


The Linked List class contains a reference of Node class type:

class Node {

public:
 int data;
 Node* next;
};


A simple CPP program to introduce a linked list:

#include <bits/stdc++.h>
using namespace std;

class Node {
public:
int data;
Node* next;
};

int main()
{
Node* head = NULL;
Node* second = NULL;
Node* third = NULL;

// allocate 3 nodes in the heap
head = new Node();
second = new Node();
third = new Node();

head->data = 1; // assign data in first node

head->next = second; // Link first node with the second node

// assign data to second node
second->data = 2;

// Link second node with the third node
second->next = third;

third->data = 3; // assign data to third node
third->next = NULL;

return 0;
}


Linked List Traversal:

#include <bits/stdc++.h>
using namespace std;

class Node {
public:
int data;
Node* next;
};

void printList(Node* n)
{
while (n != NULL) {
cout << n->data << " ";
n = n->next;
}
}

int main()
{
Node* head = NULL;
Node* second = NULL;
Node* third = NULL;

// allocate 3 nodes in the heap
head = new Node();
second = new Node();
third = new Node();

head->data = 1; // assign data in first node
head->next = second; // Link first node with second

second->data = 2; // assign data to second node
second->next = third;

third->data = 3; // assign data to third node
third->next = NULL;

printList(head);

return 0;
}

    Output: 

     1  2  3
Connect with the Author:
Instagram
Location: Greater Noida, Uttar Pradesh, India

Comments

Post a Comment

Popular posts from this blog

DATA STRUCTURE AND ALGORITHM (Array)

-
Image
 ARRAY An Array  is a collection of similar data items stored at contiguous memory locations and elements can be accessed randomly using indices of an array.  Array Array declaration by specifying size: // Array declaration by specifying size int array1[20]; // W e can also  declare an array of user specified size int n = 20; int array2[n]; Array declaration by initializing elements: // Array declaration by initializing elements int array[] = { 10, 20, 30, 40 } Array declaration by specifying size and initializing elements: // Array declaration by specifying size and initializing // elements int array[6] = { 10, 20, 30, 40 } Advantages of an Array in C++:   Random access of elements using array index. Use of less line of code as it creates a single array of multiple elements. Easy access to all the elements. Traversal through the array becomes easy using a single loop. Sorting becomes easy as it can be accomplished by writing less line of code. Disadvantages of...
Read more

DATA STRUCTURE AND ALGORITHM (Pointer)

-
Image
 POINTER Pointers are symbolic representation of addresses. They enable programs to simulate call-by-reference as well as to create and manipulate dynamic data structures.      Syntax: datatype *var_name; int *ptr; //ptr can point to an address which holds int data How to use a pointer? Define a pointer variable Assigning the address of a variable to a pointer using unary operator (&) which returns the address of that variable. Accessing the value stored in the address using unary operator (*) which returns the value of the variable located at the address specified by its operand. C++ program to illustrate Pointers in C++ #include <iostream> using namespace std; void pointer() { int var = 20; int *ptr;      //declare pointer variable //note that data type of ptr and var must be same ptr = &var; // assign the address of a variable to a pointer cout << "Value at ptr = " << ptr << "\n"; cout << "...
Read more

DATA STRUCTURE AND ALGORITHM (Structure)

-
Image
STRUCTURE Structures in C++  are user defined data types which are used to store group of items of non-similar data types.  Def : A structure is a user-defined data type in C/C++. A structure creates a data type that can be used to group items of possibly different types into a single type.  Structure Syntax Of Structure : struct structureName{ member1; member2; member3; . . . memberN; }; Structures in C++ can contain two types of members:   Data Member : These members are normal C++ variables. We can create a structure with variables of different data types in C++. Member Functions : These members are normal C++ functions. Along with variables, we can also include functions inside a structure declaration. // Data Members int roll; int age; int marks;        // Member Functions void printDetails() {      cout<< "Roll = " <<roll<< "\n" ;      cout...
Read more