Linked list on C++
Linked List is a linear data structure which comprises of elements/nodes stored at various locations not necessarily contiguous. But don’t we have arrays for keeping a list? Well, there are quite a bit of advantages of linked list. In linked list it’s much easier to insert a value or delete a value which will require more time in arrays.
It consists of nodes which can have multiple variables but alone with it has a next pointer which points to the next node in the linked list. The last node points to a NULL pointer which denotes the end of the linked List.
Structure
Let’s define it structurally –
Well, CPP does provide linked list implementation in STL but we will be covering the basics of designing a linked list by ourselves. Let’s dive in.
Linked List supports generally three operations Insert, size, delete at position. To begin with p=p→next is a the most important statement to understand. It says if p be a node in the linked list then if we want to go to the next node, we just need to assign p to it’s next. The whole linked list traversal is based on this.
- Insertion: Whenever we need to insert a node in linked list, we can either choose to insert it in the beginning or at any position given by k.
So, when we insert at the beginning, we just need to assign the temporary variable’s next to our current head and then change our head to a new temporary node.
When we have a particular position, we will do the same thing only first we will traverse to k-1thnode in the linked list and insert the new temporary node in the list.
Code Implementation –
void insertLinkedList(Node *Head,int data,int position)< if(Head == NULL)< Node *temp; temp->data = data; temp->next = NULL; *Head = temp; > else< int k = position -1; Node *temp; temp->data = data; temp->next = NULL; Node *pt = *Head; while(k-- && pt!=NULL)< pt = pt->next; > temp->next = pt->next; pt->next = temp; free(temp); free(pt); > >- Deletion: Deletion refers to deleting a node from the beginning or a given position. It works on the same algorithm as insertion. Only change that we have to make is If p points to the node to be deleted, we will traverse to the node before it and just change the next pointer to the next pointer of the ‘to be deleted’ node.
Code Implementation –
void deletenode(Node *Head,int position)< int k = position -1; Node *temp = NULL;//following ptr Node *pt = *Head; while(k-- && pt!=NULL)< temp = pt; pt = pt->next; > temp->next = pt->next; free(temp); free(pt); >- Size: This function will traverse the linked list and just return the size of the linked list.
Code Implementation –
int sizelinkedlist(Node *Head)< int count = 0; Node *pt = *Head; while(pt)< count++; pt = pt->next; > return count; >STL Linked List in CPP
CPP provide built int function for Lists which are sane sequence containers that allow non-contiguous memory allocation. STL provides list with very strong method background and makes easier to implement linked list in CPP.
list llist;[declaration of list in STL]
It has various methods like –
- Front(): returns the value of the first element.
- Back(): returns the value of the last element.
- Push_back(): inserts the new element to the end of the list.
- Size(): returns the size of the linked list.
- Reverse(): return the pointer to the reversed list.( Actually reverses the linked list also), etc.
Applications
Linked list has various applications like –
- Creating stacks and queues.
- Implementation in graphs
- Performing arithmetic operations on long integers
- Image Viewer
- Music Player
This article was a brief introduction to Linked list in CPP. Although all other problems can be solved using these basic algorithms related to Linked list.
This article tried to discuss Linked List implementation on c++. Hope this blog helps you understand and implement the concept. To practice more and build your foundation you can check out Prepbytes Courses.
Linked Lists
A set of items of the same type in which each item points to («is linked to») the next item in the list. Ordering of items is not part of the definition, therefore, we will not consider the ordering. Yet determined according to the usage.
NOTE: Since sequence of elements is not part of definition of a linked list, many other structures can be implemented using Linked Lists.
E.g. if items are ordered according to the sequence of insertion into the list, this corresponds to a stack, in which the top item is pointed by the list head pointer.
Head pointer
- List head is a special pointer to the first item in the list.
- The last node(rear) points to a NULL address
- In processing a list, any node can only be accessed after having accessed all other nodes before it. This property might also be called, in other words, Strict Sequential Access (SSA).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// implementation of LinkedList // the Node class will be given later // Author: Ali Selcuk AKYUZ // Mail: selcuk@retinarobotics.com || e174043@metu.edu.tr // Electrical and Electronics Engineering Department // Middle East Technical University - ANKARA // If any questions please send me an email using namespace std; int main () < Nodechar> *p,*q,*r; // Link the nodes with each other q = new Nodechar>('B'); // here nxtptr is passed by a nullptr by default p = new Nodechar>('A',q); r = new Nodechar>('C'); // modify the list q->InsertAfter(r); /* Call the InsertAfter method that belongs to the object pointed by q, as paramater, pass to it the address contained in r. */ cout "p:" data // "A" will be printed out cout "p_next:" NextNode()->data // "B" will be printed out cout "q:" data // "B" will be printed out cout "q_next:" NextNode()->data // "C" will be printed out cout "r:" data // "C" will be printed out p = p->NextNode(); // p now points to the node coming after the node it was // previously pointing to. cout << endl; cout "p:" data // "B" will be printed out r = q->DeleteAfter(); // copy to r the address of the node pointed by //the node pointed by the node pointed by q, and remove that node from the list Nodechar> *head; head = GetNode('A',GetNode('B',GetNode('C'))); /* Here above method, creates a list which has nodes having data A,B,C and each node pointing to the next one respectively. */ delete q; delete p; delete r; return 0; >p:A P_next:B q:B q_next:C r:C p:B
Now let us implement the Node class so that we can have a better understanding of this structure.
Let me start with the header
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// Node.h // Author: Ali Selcuk AKYUZ // Mail: selcuk@retinarobotics.com || e174043@metu.edu.tr // Electrical and Electronics Engineering Department // Middle East Technical University - ANKARA // If any questions please send me an email using namespace std; templateclass T> class Node < public: Node(); Node(const T& item, Node* ptrnext = NULL); T data; // access to the next node Node* NextNode(); // list modification methods void InsertAfter(Node* p); Node* DeleteAfter(); Node * GetNode(const T& item, Node* nextptr = NULL); private: Node * next; >; // NODE_H Here we have a default constructer, and three methods that will be explained later in the cpp part of the class implementation.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// implementation of Node class // Author: Ali Selcuk AKYUZ // Mail: selcuk@retinarobotics.com || e174043@metu.edu.tr // Electrical and Electronics Engineering Department // Middle East Technical University - ANKARA // If any questions please send me an email templateclass T> Node::Node() < // default constructor // this is to allow us to create an object without any initialization > // This constructor is just to set next pointer of a node and the data contained. templateclass T> Node::Node(const T& item,Node* ptrnext) < this->data = item; this->next = ptrnext; > templateclass T> Node*Node::NextNode() < return this->next; > // This methods inserts a node just after the node that the method belongs to // TO-DO: Consider a better implementation templateclass T> void Node::InsertAfter(Node *p) < // not to lose the rest of the list, we ought to link the rest of the // list to the Node* p first p->next = this->next; // now we should link the previous Node to Node *p , i.e the Node that we are //inserting after, this->next = p; > // Deletes the node from the list and returns the deleted node templateclass T> Node* Node::DeleteAfter() < // store the next Node in a temporary Node Node* tempNode = next; // check if there is a next node if(next != NULL) next = next->next; return tempNode; > templateclass T> Node * GetNode(const T& item, Node* nextptr = NULL) < Node* newnode; // Local ptr for new node newnode = new Node(item,nextptr); if ( newnode == NULL) < cerr "Memory allocation failed." return newnode; >After implementing the node class, now we can implement stacks, queues and the like. Let me implement these structures by using Linked List logic.
Stack, Queue Properties
Stack
If the items are ordered according to the sequence of insertion into the list, this corresponds to a stack.In other words, First In Last Out (FILO) or Last In First Out (LIFO)
Queue
A queue is a data structure consisting of a list of items and two pointers to the «front» and «rear» items in the list. Items can only inserted at the rear and removed only at the front. i.e. FIFO (First In First Out) operation.
I will implement these classes in another article.