A Linked List is a data structure holding elements in a sequence. The elements, however, are not in a contiguous location in the RAM. Rather the elements are kept in nodes and each node can point to the next node . The nodes do not have to be located in contiguous locations in the RAM. The advantage of this structure is that the nodes can be inserted and removed easily without moving the other nodes . The disadvantage is that random access is difficult. It does not have indexes like arrays and we need to traverse the list in order to reach a particular element.
File: "MyLinkedList.h"
#include <bits/stdc++.h> using namespace std; class Node { public: int data; Node* next; Node( int value ) { data = value ; next = NULL ; } Node( int value , Node* nextP) { data = value ; next = nextP ; } }; //------------------------------------------------------ class MyLinkedList { public: Node* head = NULL ; int noItems = 0 ; void add( int value ) { if ( head == NULL ) { Node* ptrNode = new Node( value ) ; head = ptrNode ; } else { Node* newNode = new Node( value, head ) ; head = newNode ; } } void remove( int value ) { Node* temp = head ; Node* previous = NULL ; while ( temp != NULL ) { if( temp->data == value ) { if ( temp == head ) //very first element { head = head->next ; delete temp ; } else { previous->next = temp->next ; delete temp ; } break ; } previous = temp ; temp = temp->next ; } //while } bool search( int value ) { Node* temp = head ; while ( temp != NULL ) { if ( temp->data == value ) return true ; temp = temp->next ; } //while return false ; } void print( ) { Node* temp = head ; cout << "Start of print: --------------" << endl ; while ( temp != NULL ) { cout << temp->data << " " ; temp = temp->next ; } //while cout << endl ; cout << "End of print: --------------" << endl ; } void reverseList() { Node* previous = NULL ; Node* ptr1 = head ; Node* t1 ; while ( ptr1 != NULL ) { t1 = ptr1->next ; ptr1->next = previous ; previous = ptr1 ; ptr1 = t1 ; } head = previous ; } };
File: "driver.cpp"
#include "MyLinkedList.h"int main(){ MyLinkedList list1 ; list1.add( 10 ) ; list1.add( 11 ) ; list1.add( 12 ) ; list1.remove( 11 ) ; list1.print() ; list1.remove( 12 ) ; list1.print() ; return 0;}
Ex 1
Add and implement the following function to the "MyLinked:ist.h"
//inserts the value such that the list is sorted in an ascending order
void insert( int value )
Doubly Linked List
A doubly linked list has nodes that contain a pointer to the previous node.
head ---> node1 node2
NULL <-- node1 <--
--> node2 --> NULL
File: "MyDoublyLinkedList"
#include <bits/stdc++.h> using namespace std; class Node { public: int data; Node* next ; Node* previous ; Node( int value ) { data = value ; next = NULL ; previous = NULL ; } Node( int value , Node* nextP) { data = value ; next = nextP ; previous = NULL ; } Node( int value , Node* nextP , Node* previousP ) { data = value ; next = nextP ; previous = previousP ; } }; //------------------------------------------------------ class MyDoublyLinkedList { public: Node* head = NULL ; int noItems = 0 ; void add( int value ) { if ( head == NULL ) { Node* ptrNode = new Node( value ) ; head = ptrNode ; } else { Node* newNode = new Node( value, head ) ; head->previous = newNode ; head = newNode ; } } void remove( int value ) { Node* temp = head ; while ( temp != NULL ) { if( temp->data == value ) { if ( temp == head ) //very first element { if ( head->next != NULL ) head->next->previous = NULL ; head = head->next ; delete temp ; } else { temp->previous->next = temp->next ; if ( temp->next != NULL ) temp->next->previous = temp->previous ; delete temp ; } break ; } //if( temp->data == value ) temp = temp->next ; } //while } bool search( int value ) { Node* temp = head ; while ( temp != NULL ) { if ( temp->data == value ) return true ; temp = temp->next ; } //while return false ; } void print( ) { Node* temp = head ; cout << "Start of print: --------------" << endl ; while ( temp != NULL ) { cout << temp->data << " " ; if ( temp->previous != NULL ) cout << "Previous:" << temp->previous->data << endl ; else cout << "Previous is null :" << endl ; temp = temp->next ; } //while cout << endl ; cout << "End of print: --------------" << endl ; } };
File: "l2.cpp"
//------------------------------------------------------#include "MyDoublyLinkedList.h"// Driver codeint main(){ MyDoublyLinkedList list1 ; list1.add( 15 ) ; list1.add( 10 ) ; // list1.add( 12 ) ; // list1.remove( 11 ) ; // list1.insert( 10 ) ; list1.insert( 15 ) ; // list1.insert( 13 ) ; // list1.reverseList() ; list1.print() ;/* list1.add( 10 ) ; list1.add( 11 ) ; list1.add( 12 ) ; list1.remove( 11 ) ; list1.print() ; list1.remove( 12 ) ; list1.print() ; list1.remove( 10 ) ; list1.print() ; */ /* list1.add( 10 ) ; list1.add( 11 ) ; list1.add( 12 ) ; list1.reverseList() ; list1.print() ; */ //list1.insert( 15 ) ; //list1.insert( 10 ) ; //list1.insert( 20 ) ; //list1.print() ; return 0;}Ex 2:
Add in the code for the functions "insert" .
Do not use a variable "previous" but instead use the "previous" pointer in the node.
Circular Linked List
A circular linked list has the last node pointing to the first node instead of the value "NULL" . A single node has the next node pointing to itself.
Ex3:
Using the single linked list as a starting point. Implement the circular linked list. Use a variable called "tail" that points to the last node. Also make sure the print function does not go in an infinite loop. Implement "insert" and "clear" functions.
File: "MyCircularList.h"
#include <bits/stdc++.h> using namespace std; class Node { public: int data; Node* next; Node( int value ) { data = value ; next = NULL ; } Node( int value , Node* nextP) { data = value ; next = nextP ; } }; //------------------------------------------------------ class MyCircularLinkedList { public: Node* head = NULL ; Node* tail = NULL ; int noItems = 0 ; void add( int value ) { } void remove( int value ) { Node* temp = head ; Node* previous = NULL ; while ( temp != NULL ) { if( temp->data == value ) { if ( temp == head ) //very first element { head = head->next ; tail->next = head ; noItems-- ; if ( noItems == 0 ) { head = NULL ; tail = NULL ; } delete temp ; } else { //Removing the last element. if ( temp == tail ) tail = previous ; previous->next = temp->next ; delete temp ; } break ; } previous = temp ; temp = temp->next ; } //while } bool search( int value ) { Node* temp = head ; while ( temp != NULL ) { if ( temp->data == value ) return true ; temp = temp->next ; if ( temp == head ) break ; } //while return false ; } void insert( int value ) { } //void insert( int value ) void print( ) { Node* temp = head ; cout << "Start of print: --------------" << endl ; if ( tail != NULL ) { cout << "tail data:" << tail->data << " tail next:" << tail->next->data << endl ; } while ( temp != NULL ) { cout << temp->data << " " ; temp = temp->next ; if ( temp == head ) break ; } //while cout << endl ; cout << "End of print: --------------" << endl ; } void clear( ) { } };
File: "l3.cpp"
//------------------------------------------------------#include "MyCircularLinkedList.h"// Driver codeint main(){ MyCircularLinkedList list1 ; /* //test case 1 single node list1.add( 10 ) ; list1.print() ; //test case 2 nodes list1.add( 20 ) ; list1.print() ; list1.remove( 20 ) ; list1.print() ; list1.remove( 10 ) ; list1.print() ; */ list1.add( 30 ) ;list1.add( 20 ) ;list1.add( 10 ) ; list1.remove( 20 ) ; list1.print() ; list1.clear() ; list1.print() ; list1.insert( 10 ) ; list1.print() ; list1.insert( 20 ) ; list1.print() ; list1.insert( 15 ) ; list1.print() ; /* list1.add( 11 ) ; list1.add( 12 ) ; list1.remove( 11 ) ; list1.print() ; */ //list1.remove( 12 ) ; //list1.print() ; //list1.remove( 10 ) ; //list1.print() ; */ /* list1.add( 10 ) ; list1.add( 11 ) ; list1.add( 12 ) ; list1.reverseList() ; list1.print() ; */ // list1.insert( 15 ) ; //list1.insert( 10 ) ; //list1.insert( 20 ) ; // list1.print() ; return 0;}
Ex 3:
Implement the add and clear function for a circular linked
list.
Solutions
1)
2)
Source Code