Linked Lists
Linked Lists are data structures that are similar to arrays but are not stored in contiguous memory. Linked Lists use pointers to access the next node. Logically a linked list looks like,
Each node has two variables, first variable stores the data value and the second variable is a pointer variable that points to the next node in the linked list.
Arrays have O(n) Insertion operation and O(n) deletion operation [at the first position], whereas in Linked Lists these operations are O(1).
However, we cannot access a linked list element directly like in array using index. Instead we have to parse through a linked list sequentially using pointers.
Also, array size is fixed whereas linked lists are expandable. Linked lists also consume extra space because of pointer.
We can create a Linked List in C++ by defining a structure for node as :
Here LLNode contains a data value and a pointer to point to the next node in the Linked List.
Example,
The diagram for the Linked List created in the example, would look like :
Alternatively, we can create the nodes dynamically using malloc as :
We can do list traversal by using a while loop from head, until pointer points to NULL. Example of function that prints each node's data value in linked list :
The insertion and deletion operations in Linked Lists can be performed by changing pointers of nearby nodes to the position where operation is to be performed.
Each node has two variables, first variable stores the data value and the second variable is a pointer variable that points to the next node in the linked list.
Arrays have O(n) Insertion operation and O(n) deletion operation [at the first position], whereas in Linked Lists these operations are O(1).
However, we cannot access a linked list element directly like in array using index. Instead we have to parse through a linked list sequentially using pointers.
Also, array size is fixed whereas linked lists are expandable. Linked lists also consume extra space because of pointer.
We can create a Linked List in C++ by defining a structure for node as :
struct LLNode {
int data;
struct LLNode * pointer; // pointer that points to Node in Linked List
};
Here LLNode contains a data value and a pointer to point to the next node in the Linked List.
Example,
#include <string>
#include <iostream>
using namespace std;
struct LLNode {
int data;
struct LLNode * pointer; // pointer that points to Node in Linked List
};
int main()
{
struct LLNode *l1 = new struct LLNode;
struct LLNode *l2 = new struct LLNode;
struct LLNode *head = l1;
head->data = 2;
l2->data = 4;
l1->pointer = l2; // l1 points to l2
l2->pointer = null;
cout<<l1->pointer->data<<endl; // print data value of node that l1 points to
cout<<l1->data<<endl;
delete l1;
delete l2;
return 1;
}
int main()
{
struct LLNode* head = NULL;
struct LLNode* l1 = NULL;
struct LLNode* l2 = NULL;
l1 = (struct LLNode*)malloc(sizeof(struct LLNode));
l2 = (struct LLNode*)malloc(sizeof(struct LLNode));
head = l1;
head->data = 2;
l2->data = 4;
l1->pointer = l2; // l1 points to l2
cout<<l1->pointer->data<<endl; // print data value of node that l1 points to
cout<<l1->data<<endl;
delete l1;
delete l2;
return 1;
}
We can do list traversal by using a while loop from head, until pointer points to NULL. Example of function that prints each node's data value in linked list :
void printlist(struct LLNode * head) {
int i = 1;
while (head)
{
cout<<head->data<<" Node : "<<i<<endl;
i++;
head = head->pointer;
}
}
The insertion and deletion operations in Linked Lists can be performed by changing pointers of nearby nodes to the position where operation is to be performed.
Comments
Post a Comment