Linked list with two values C++ Hướng dẫn FULL

Kinh Nghiệm về Linked list with two values C++ Chi Tiết

Quý khách đang tìm kiếm từ khóa Linked list with two values C++ được Update vào lúc : 2022-12-17 09:42:15 . Với phương châm chia sẻ Thủ Thuật về trong nội dung bài viết một cách Chi Tiết Mới Nhất. Nếu sau khi tìm hiểu thêm nội dung bài viết vẫn ko hiểu thì hoàn toàn có thể lại Comments ở cuối bài để Admin lý giải và hướng dẫn lại nha.

C++ Tutorial – Linked List Examples – 2022

bogotobogo.com site search:

A linked list is a basic data structure where each item contains the information that we need to get to the next item.

The main advantage of linked lists over arrays is that the links provide us with the capability to rearrange the item efficiently. This flexibility is gained the expense of quick access to any arbitrary item in the list, because the only way to access to an item in the list is to follow links from the beginning.

The following examples are for the linked list. Inside each example, we have several operations:

Reversing the linked list (#1, #3, #4)

Copying the linked list(#1)

Detecting circular (loop) linked list(#5)

Comparing the two linked list(#1)

Deleting the linked list(#1)

Adding, deleting, inserting, and searching a node (all examples)

Stack implementation with linked list (#6, #7)

Finding intersection and union of two lists (#8)

Also, there is another set of linked list quiz.

#include

using namespace std;

struct Node

int data;

Node* next;

;

// only for the 1st Node

void initNode(struct Node *head,int n)

head->data = n;

head->next =NULL;

// apending

void addNode(struct Node *head, int n)

Node *newNode = new Node;

newNode->data = n;

newNode->next = NULL;

Node *cur = head;

while(cur)

if(cur->next == NULL)

cur->next = newNode;

return;

cur = cur->next;

void insertFront(struct Node **head, int n)

Node *newNode = new Node;

newNode->data = n;

newNode->next = *head;

*head = newNode;

struct Node *searchNode(struct Node *head, int n)

Node *cur = head;

while(cur)

if(cur->data == n) return cur;

cur = cur->next;

cout << “No Node ” << n << ” in list.n”;

bool deleteNode(struct Node **head, Node *ptrDel)

Node *cur = *head;

if(ptrDel == *head)

*head = cur->next;

delete ptrDel;

return true;

while(cur)

if(cur->next == ptrDel)

cur->next = ptrDel->next;

delete ptrDel;

return true;

cur = cur->next;

return false;

/* reverse the list */

struct Node* reverse(struct Node** head)

Node *parent = *head;

Node *me = parent->next;

Node *child = me->next;

/* make parent as tail */

parent->next = NULL;

while(child)

me->next = parent;

parent = me;

me = child;

child = child->next;

me->next = parent;

*head = me;

return *head;

/* Creating a copy of a linked list */

void copyLinkedList(struct Node *node, struct Node **pNew)

if(node != NULL)

*pNew = new Node;

(*pNew)->data = node->data;

(*pNew)->next = NULL;

copyLinkedList(node->next, &((*pNew)->next));

/* Compare two linked list */

/* return value: same(1), different(0) */

int compareLinkedList(struct Node *node1, struct Node *node2)

static int flag;

/* both lists are NULL */

if(node1 == NULL && node2 == NULL)

flag = 1;

else node2 == NULL)

flag = 0;

else if(node1->data != node2->data)

flag = 0;

else

compareLinkedList(node1->next, node2->next);

return flag;

void deleteLinkedList(struct Node **node)

struct Node *tmpNode;

while(*node)

tmpNode = *node;

*node = tmpNode->next;

delete tmpNode;

void display(struct Node *head)

Node *list = head;

while(list)

cout << list->data << ” “;

list = list->next;

cout << endl;

cout << endl;

int main()

struct Node *newHead;

struct Node *head = new Node;

initNode(head,10);

display(head);

addNode(head,20);

display(head);

addNode(head,30);

display(head);

addNode(head,35);

display(head);

addNode(head,40);

display(head);

insertFront(&head;,5);

display(head);

int numDel = 5;

Node *ptrDelete = searchNode(head,numDel);

if(deleteNode(&head;,ptrDelete))

cout << “Node “<< numDel << ” deleted!n”;

display(head);

cout << “The list is reversedn”;

reverse(&head;);

display(head);

cout << “The list is copiedn”;

copyLinkedList(head,&newHead;);

display(newHead);

cout << “Comparing the two lists…n”;

cout << “Are the two lists same?n”;

if(compareLinkedList(head,newHead))

cout << “Yes, they are same!n”;

else

cout << “No, they are different!n”;

cout << endl;

numDel = 35;

ptrDelete = searchNode(newHead,numDel);

if(deleteNode(&newHead;,ptrDelete))

cout << “Node “<< numDel << ” deleted!n”;

cout << “The new list after the delete isn”;

display(newHead);

cout << “Comparing the two lists again…n”;

cout << “Are the two lists same?n”;

if(compareLinkedList(head,newHead))

cout << “Yes, they are same!n”;

else

cout << “No, they are different!n”;

cout << endl;

cout << “Deleting the copied listn”;

deleteLinkedList(&newHead;);

display(newHead);

return 0;

Output from the run:

10

10 20

10 20 30

10 20 30 35

10 20 30 35 40

5 10 20 30 35 40

Node 5 deleted!

10 20 30 35 40

The list is reversed

40 35 30 20 10

The list is copied

40 35 30 20 10

Comparing the two lists…

Are the two lists same?

Yes, they are same!

Node 35 deleted!

The new list after the delete is

40 30 20 10

Comparing the two lists again…

Are the two lists same?

No, they are different!

Deleting the copied list

#include

using namespace std;

struct node

int data;

struct node * next;

;

node *head = NULL;

// returning the pointer to the element

// whose data is less than or equal to input data

struct node *searchNode(int n)

if(head == NULL) return head;

node *cur = head;

node *prev = head;

while(cur)

if(cur->data == n) return cur;

if(cur->data > n) return prev;

prev = cur;

cur = cur->next;

// returning the pointer to the element

// whose data is equal to input data

struct node *searchNode2(int n)

if(head == NULL) return head;

node *cur = head;

node *prev = head;

while(cur)

if(cur->data == n) return cur;

prev = cur;

cur = cur->next;

return cur;

void addNode(int n)

node *newNode = new node;

newNode->data = n;

newNode->next = NULL;

if(head == NULL)

head = newNode;

return;

node *cur = head;

while(cur)

if(cur->next == NULL)

cur->next = newNode;

return;

cur = cur->next;

void insertNode(int n)

node *ptr = searchNode(n);

node *newNode = new node;

newNode->data = n;

node *cur = head;

while(cur)

if(cur == ptr )

newNode->next = cur->next;

cur->next = newNode;

return;

cur = cur->next;

void deleteNode(int n)

node *ptr = searchNode(n);

if(ptr == NULL)

cout << “No node with data = ” << n << endl;

if(ptr == head)

head = ptr->next;

return;

node *cur = head;

node *prev = head;

while(cur)

if(cur == ptr)

prev->next = cur->next;

return;

prev = cur;

cur = cur->next;

void display()

struct node *list = head;

while(list)

cout << list->data <<” “;

list = list->next;

cout << endl;

int main()

addNode(10);

display();

addNode(20);

display();

addNode(40);

display();

addNode(50);

display();

insertNode(30);

display();

deleteNode(40);

display();

return 0;

// linked list example – using struct

#include

#include

using namespace std;

struct node * initNode( char *, int );

void displayNode( struct node * );

void displayList( struct node * );

void addNode( struct node * );

struct node * searchName( struct node *, char * );

void deleteNode( struct node * );

void insertNode( struct node * );

void deleteList( struct node * );

struct node

char name[20];

int id;

struct node *next;

;

struct node *head = (struct node *) NULL;

struct node *tail = (struct node *) NULL;

// allocates memory for the node

// assign values to the thành viên of the structure

struct node * initNode( char *name, int id )

struct node *ptr = new node;

// error? then just return

if( ptr == NULL )

return static_cast(NULL);

// assign it

// then return pointer to ne node

else

strcpy( ptr->name, name );

ptr->id = id;

return ptr;

// adding to the end of list

void addNode( struct node *newnode )

// if there is no node, put it to head

if( head == NULL )

head = newnode;

tail = newnode;

// link in the new_node to the tail of the list

// then mark the next field as the end of the list

// adjust tail to point to the last node

tail->next = newnode;

newnode->next = NULL;

tail = newnode;

void insertNode( struct node *newnode )

struct node *temp, *prev;

if( head == NULL ) // if an empty list,

head = newnode; // set ‘head’ to it

tail = newnode;

head->next = NULL; // set end of list to NULL

return;

temp = head; // start beginning of list

// while currentname < newname

while( strcmp( temp->name, newnode->name) < 0 )

// to be inserted then

temp = temp->next; // goto the next node in list

if( temp == NULL ) // don’t go past end of list

break;

// set previous node before we insert

// first check to see if it’s inserting

if( temp == head ) // before the first node

newnode->next = head; // link next field to original list

head = newnode; // head adjusted to new node

else // it’s not the first node

prev = head; // start of the list,

while( prev->next != temp ) // will cycle to node before temp

prev = prev->next;

prev->next = newnode; // insert node between prev and next

newnode->next = temp;

if( tail == prev ) // if the new node is inserted the

tail = newnode; // end of the list the adjust ‘end’

struct node * searchName( struct node *ptr, char *name )

while( strcmp( name, ptr->name ) != 0 )

ptr = ptr->next;

if( ptr == NULL )

break;

return ptr;

struct node* searchId(struct node* ptr, int id)

while( id != ptr->id )

ptr = ptr->next;

if( ptr == NULL )

break;

return ptr;

void reverse() head->next == NULL) return;

// Starting 2nd list as ‘me’ and ‘head’ is now ‘me->next’

// and ‘head->next’ is pointing to NULL

// So, the 3rd list is now ‘child’ of ‘me’

node *parent = head;

node *me = head->next;

node *child = me->next;

// convert head to tail

parent->next = NULL;

while(child != NULL)

me->next = parent;

parent = me;

me = child;

child = child->next;

// when me reached the tail

// me becomes head

head = me;

// the head is now pointing to the 2nd last node

head->next = parent;

void deleteNode( struct node *ptr )

struct node *temp, *prev;

temp = ptr; // node to be deleted

prev = head; // start of the list, will cycle to node before temp

if( temp == prev ) // deleting first node?

head = head->next; // moves head to next node

if( tail == temp ) // is it end, only one node?

tail = tail->next; // adjust end as well

delete temp ; // không lấy phí up space

else // if not the first node, then

while( prev->next != temp ) // move prev to the node before

prev = prev->next; // the one to be deleted

prev->next = temp->next; // link previous node to next

if( tail == temp ) // if this was the end node,

tail = prev; // then reset the end pointer

delete temp; // không lấy phí up space

void deleteList( struct node *ptr )

struct node *temp;

if( head == NULL ) return; // don’t try to delete an empty list

if( ptr == head ) // if we are deleting the entire list

head = NULL; // then reset head and

tail = NULL; // end to empty

else

temp = head; // if it’s not the entire list, readjust end

while( temp->next != ptr ) // locate previous node to ptr

temp = temp->next;

tail = temp; // set end to node before ptr

while( ptr != NULL ) // while there are still nodes to delete

temp = ptr->next; // record address of next node

delete ptr; // không lấy phí this node

ptr = temp; // point to next node to be deleted

void displayNode( struct node *ptr )

cout << ptr->id << “: ” << ptr->name << endl;

void displayList( struct node *ptr )

while( ptr != NULL )

displayNode( ptr );

ptr = ptr->next;

#include

using namespace std;

int main()

char* name;

int id, ch = 1;

struct node *ptr;

// add

ptr = initNode( “s1”, 1 );

addNode(ptr);

ptr = initNode( “s2”, 2 );

addNode(ptr);

ptr = initNode( “s3”, 3 );

addNode(ptr);

ptr = initNode( “s4”, 4 );

addNode(ptr);

ptr = initNode( “s5”, 5 );

addNode(ptr);

displayList(head);

// delete

name = “s2”;

ptr = searchName(head, name );

if( ptr == NULL )

cout << “nName: ” << name << ” not found” << endl;

else

cout << “nDeleting a node … “;

displayNode(ptr);

deleteNode( ptr );

displayList(head);

// insert

name = “s2”;

id = 2;

ptr = initNode( name, id );

insertNode( ptr );

cout << “nInserting a node … “;

displayNode(ptr);

displayList(head);

// reverse

cout << “nReversing the list … n”;

reverse();

displayList(head);

// delete

cout << “nIn the end, deleting the list … n”;

deleteList(head);

displayList(head);

return 0;

// linked list example – using struct inside a class

#include

#include

using namespace std;

class list

public:

struct node

int id;

string name;

struct node *next;

*head, *tail, *ptr;

list():head(NULL),tail(NULL) // constructor

~list(); // destructor

struct list::node* searchName(struct list::node*, string);

struct list::node* searchId(struct list::node*, int);

struct list::node* initNode(string, int);

void reverse();

void addNode( struct list::node*);

void insertNode( struct list::node*);

void deleteNode( struct list::node*);

void deleteList( struct list::node*);

void displayList( struct list::node*)const ;

void displayNode( struct list::node*) const;

;

list::~list()

node *current,*temp;

current = head;

temp = head;

while(current != NULL)

current = current->next;

delete temp;

temp = current;

struct list::node* list::initNode(string s, int i)

struct node *ptr = new node;

// error? then just return

if( ptr == NULL )

return static_cast(NULL);

// assign it

// then return pointer to ne node

else

ptr->name = s ;

ptr->id = i;

return ptr;

// adding to the end of list

void list::addNode( struct node *newNode )

// if there is no node, put it to head

if( head == NULL )

head = newNode;

tail = newNode;

// link in the new_node to the tail of the list

// then mark the next field as the end of the list

// adjust tail to point to the last node

tail->next = newNode;

newNode->next = NULL;

tail = newNode;

void list::insertNode( struct node *newnode )

struct node *temp, *prev;

if( head == NULL ) // if an empty list,

head = newnode; // set ‘head’ to it

tail = newnode;

head->next = NULL; // set end of list to NULL

return;

temp = head; // start beginning of list

// while currentname < newname

while( temp->name < newnode->name) // to be inserted then

temp = temp->next; // goto the next node in list

if( temp == NULL ) // don’t go past end of list

break;

// set previous node before we insert

// first check to see if it’s inserting

if( temp == head ) // before the first node

newnode->next = head; // link next field to original list

head = newnode; // head adjusted to new node

else // it’s not the first node

prev = head; // start of the list,

while( prev->next != temp )

prev = prev->next; // will cycle to node before temp

prev->next = newnode; // insert node between prev and next

newnode->next = temp;

if( tail == prev ) // if the new node is inserted the

tail = newnode; // end of the list the adjust ‘end’

struct list::node* list::searchName(struct node* ptr, string name)

while( name != ptr->name )

ptr = ptr->next;

if( ptr == NULL )

break;

return ptr;

struct list::node* list::searchId(struct node* ptr, int id)

while( id != ptr->id )

ptr = ptr->next;

if( ptr == NULL )

break;

return ptr;

void list::reverse()

void list::deleteNode( struct list::node *ptr )

struct node *temp, *prev;

temp = ptr; // node to be deleted

prev = head; // start of the list, will cycle to node before temp

if( temp == prev ) // deleting first node?

head = head->next; // moves head to next node

if( tail == temp ) // is it end, only one node?

tail = tail->next; // adjust end as well

delete temp ; // không lấy phí up space

else // if not the first node, then

while( prev->next != temp ) // move prev to the node before

prev = prev->next; // the one to be deleted

prev->next = temp->next; // link previous node to next

if( tail == temp ) // if this was the end node,

tail = prev; // then reset the end pointer

delete temp; // không lấy phí up space

void list::deleteList( struct node *ptr )

struct node *temp;

if( head == NULL ) return; // don’t try to delete an empty list

if( ptr == head ) // if we are deleting the entire list

head = NULL; // then reset head and

tail = NULL; // end to empty

else

temp = head; // if it’s not the entire list, readjust end

while( temp->next != ptr ) // locate previous node to ptr

temp = temp->next;

tail = temp; // set end to node before ptr

while( ptr != NULL ) // whilst there are still nodes to delete

temp = ptr->next; // record address of next node

delete ptr; // không lấy phí this node

ptr = temp; // point to next node to be deleted

void list::displayNode( struct list::node *ptr ) const

cout << ptr->id << “: ” << ptr->name << endl;

void list::displayList( struct list::node *ptr ) const

if(!ptr) cout << “Nothing to display” << endl;

while(ptr)

displayNode(ptr);

ptr = ptr->next;

int main()

int id;

string name;

list myList;

list::node* ptr;

// add

ptr = myList.initNode( “s1”, 1 );

myList.addNode(ptr);

ptr = myList.initNode( “s2”, 2 );

myList.addNode(ptr);

ptr = myList.initNode( “s3”, 3 );

myList.addNode(ptr);

ptr = myList.initNode( “s4”, 4 );

myList.addNode(ptr);

ptr = myList.initNode( “s5”, 5 );

myList.addNode(ptr);

myList.displayList(myList.head);

// delete

name = “s2”;

ptr = myList.searchName( myList.head, name );

if( ptr == NULL )

cout << “nName: ” << name << ” not found” << endl;

else

cout << “nDeleting a node … “;

myList.displayNode(ptr);

myList.deleteNode( ptr );

myList.displayList(myList.head);

// insert

name = “s2”;

id = 2;

ptr = myList.initNode( name, id );

myList.insertNode( ptr );

cout << “nInserting a node … “;

myList.displayNode(ptr);

myList.displayList(myList.head);

// reverse

cout << “nReversing the list … n”;

myList.reverse();

myList.displayList(myList.head);

// delete

cout << “nIn the end, deleting the list … n”;

myList.deleteList(myList.head);

myList.displayList(myList.head);

return 0;

Example 5A – Detecting Circular (Loop) Linked List

/* This code has the following */

/*

1. Adding Nodes

2. Function returning the size of the list

3. Making the list circular (loop)

4. Detecting circular list

5. Recursive printing

*/

#include

using namespace std;

struct Node

int data;

Node * next;

;

Node *root = 0;

void addNode(int n)

if(root==0)

root = new Node;

root->data = n;

root->next = 0;

return;

Node *cur = root;

while(cur)

if(cur->next == 0)

Node *ptr = new Node;

ptr -> data = n;

ptr -> next = 0;

cur -> next = ptr;

return;

cur = cur->next;

void makeCircular()

int sizeOfList()

Node *cur = root;

int size = 0;

while(cur)

size++;

if(cur->next == 0)

return size;

cur = cur->next;

return size;

bool detectCircular()

void printRecursive(Node *ptr)

if(!ptr)

cout << endl;

return;

cout << ptr->data << ” “;

printRecursive(ptr->next);

int main(int argc, char **argv)

addNode(10);addNode(20);addNode(30);addNode(40);addNode(50);

addNode(60);addNode(70);addNode(80);addNode(90);addNode(100);

printRecursive(root);

cout << “size of list = ” << sizeOfList() << endl;

makeCircular();

if(detectCircular()) cout <<“Circularn”;

else cout << “Normaln”;

Output from the run:

10 20 30 40 50 60 70 80 90 100

size of list = 10

20,30

30,50

40,70

50,90

60,10

70,30

80,50

90,70

100,90

10,10

Circular

Example 5B – Detecting Circular (Loop) Linked List (Generic Class with Template)

#include

#include

using namespace std;

template

class LinkedList

private:

struct node

T data;

node * next;

*head;

public:

LinkedList();

~LinkedList();

void add(T d);

void remove(T d);

void clear();

void makeCircular();

bool isCircular();

void display(const char* s);

;

template

LinkedList::LinkedList()

head = NULL;

template

LinkedList::~LinkedList()

node *p., *q;

p. = head;

if(p. == NULL) return;

while(p.)

q = p.->next;

delete p.;

p. = q;

template

void LinkedList::add(T d)

node *p., *q;

if(head == NULL)

head = new node;

head->data = d;

head->next = NULL;

return;

p. = head;

while(p.->next != NULL)

p. = p.->next;

q = new node;

q->data = d;

q->next = NULL;

p.->next = q;

template

void LinkedList::remove(T d)

node *p., *q;

if(head == NULL) return;

p. = head;

while(p.)

if(p.->data == d)

q->next = p.->next;

delete p.;

return;

q = p.;

p. = p.->next;

template

void LinkedList::clear()

node *p., *q;

if(head == NULL) return;

p. = head;

while(p.)

q = p.->next;

delete p.;

if(q != head)

head = NULL;

return;

p. = q;

template

void LinkedList::makeCircular()

node *p.;

if(head == NULL

template

bool LinkedList::isCircular()

head->next == NULL) return false;

p. = head;

pp = head;

while(pp)

p. = p.->next;

if(pp->next == NULL) return false;

pp = (pp->next)->next;

if(p. == pp) return true;

return false;

template

void LinkedList::display(const char* s)

node *p.;

if(head == NULL) return;

p. = head;

while(p.)

if(s == “string”)

cout << p.->data << endl;

else

cout << p.->data << ‘ ‘;

p. = p.->next;

if(p. != NULL)

if(p. == head) return;

if(s == “integer”) cout << endl;

int main()

LinkedList sList;

sList.add(“Wolfgang Amadeus Mozart”);

sList.add(“Franz Peter Schubert”);

sList.add(“Pyotr Ilyich Tchaikovsky”);

sList.add(“Clude-Achille Debussy”);

sList.add(“Camille Saint-Saens”);

sList.display(“string”);

sList.clear();

LinkedList iList;

iList.add(40);

iList.add(50);

iList.add(60);

iList.add(70);

iList.add(80);

iList.add(90);

iList.add(100);

iList.add(10);

iList.add(20);

iList.add(30);

iList.display(“integer”);

/* link last element to the first */

iList.makeCircular();

if(iList.isCircular()) cout <<“This is circular listn”;

iList.display(“integer”);

iList.clear();

cout << “ndisplay after clear()n”;

iList.display(“integer”);

return 0;

Output from the run is:

Wolfgang Amadeus Mozart

Franz Peter Schubert

Pyotr Ilyich Tchaikovsky

Clude-Achille Debussy

Camille Saint-Saens

40 50 60 70 80 90 100 10 20 30

This is circular list

40 50 60 70 80 90 100 10 20 30

display after clear()

Example 6 – Stack Using Linked List

This stack is using linked list as its data structure.

/* Stack operations */

#include

using namespace std;

typedef struct Element

void *data;

struct Element *next;

Element;

bool push(Element **top, void *data)

Element *elem = new Element;

if(!elem) return false;

elem->data = data;

elem->next = *top;

*top = elem;

return true;

bool createStack(Element **top)

*top = NULL;

return true;

bool pop(Element **top, void **data )

Element *elem;

if( !(elem = *top) ) return false;

*data = elem->data;

*top = elem->next;

delete elem;

return true;

bool deleteStack(Element **top)

Element *elem;

while(*top)

elem = (*top)->next;

delete *top;

*top = elem;

return true;

void printStack(Element *top)

if(top==NULL)

cout << “Empty!” << endl;

Element *cur = top;

while(cur)

cout << *(static_cast(cur->data)) << ” “;

cur = cur->next;

cout << endl << endl;

int main()

Element *head;

createStack(&head;);

int n1 = 10, n2 = 20, n3 = 30, n4 = 40, n5 = 50;

push(&head;, &n1;);

push(&head;, &n2;);

push(&head;, &n3;);

push(&head;, &n4;);

push(&head;, &n5;);

printStack(head);

void * n;

pop(&head;, &n;);

cout << “popped ” << *(static_cast(n)) << endl;

pop(&head;, &n;);

cout << “popped ” << *(static_cast(n)) << endl;

cout << endl;

printStack(head);

cout << “deleting stack…” << endl;

deleteStack(&head;);

printStack(head);

Output:

50 40 30 20 10

popped 50

popped 40

30 20 10

deleting stack…

Empty!

Example 7 – Stack Class Using Linked List

#include

using namespace std;

class Stack

public:

Stack();

~Stack();

void push(int);

int pop();

int peek();

friend void print(Stack&);

private:

typedef struct node

node *next;

int data;

NODE;

NODE *top;

;

Stack::Stack()

top = NULL;

Stack::~Stack()

while(top)

NODE *tmp = top;

top = top->next;

delete tmp;

void Stack::push(int n)

NODE *ptr = new NODE;

ptr->next = top;

ptr->data = n;

top = ptr;

int Stack::pop()

NODE *tmp = top;

int val = top->data;

top = top->next;

delete tmp;

return val;

int Stack::peek()

return top->data;

void print(Stack &s;)

Stack::NODE *cur = s.top;

while(cur)

cout << cur->data << ” “;

cur = cur->next;

cout << endl;

int main()

Stack *st = new Stack;

st->push(10);

st->push(20);

st->push(30);

st->push(40);

st->push(50);

print(*st);

st->pop();

st->pop();

print(*st);

cout << “current top=” << st->peek();

return 0;

Output:

50 40 30 20 10

30 20 10

current top=30

Example 7B – Stack Class Using Linked List

The code below is almost the same as the code in Example 6 except it’s using Stack class.

The code below is almost the same as the code in Example 7 except it’s using void* for the data type.

#include

using namespace std;

class Stack

public:

Stack();

~Stack();

void push(void *data);

void *pop();

void print();

protected:

typedef struct Element

struct Element *next;

void *data;

Element;

Element *top;

;

Stack::Stack()

top = NULL;

Stack::~Stack()

while(top)

Element *elm = top->next;

delete top;

top = elm;

void Stack::push(void *data)

Element *elm = new Element;

elm->data = data;

elm->next = top;

top = elm;

void *Stack::pop()

void *data;

if(top == NULL) return data;

data = top->data;

Element *elm = top;

top = elm->next;

delete elm;

return data;

void Stack::print()

Element *elm = top;

while(elm)

cout << *(static_cast(elm->data)) << ” ” ;

elm = elm->next;

cout << endl;

int main()

Stack *st = new Stack;

int n1 = 10;

int n2 = 20;

int n3 = 30;

int n4 = 40;

int n5 = 50;

st->push(&n1;);

st->push(&n2;);

st->push(&n3;);

st->push(&n4;);

st->push(&n5;);

st->print();

cout << *(static_cast(st->pop()))<< ” popedn”;

cout << *(static_cast(st->pop()))<< ” popedn”;

st->print();

cout << endl;

Output:

50 40 30 20 10

50 poped

40 poped

30 20 10

Example 7C – Stack Class Using Linked List with Query for Minimum Value

This stack class can return its minimum element. All operations (push(), pop(), and peekMin()) are O(1) not O(n). Usual approach for query would be traverse each element to get the minimum, and it will ends up with O(n) complexity. So, to have constant time operation, we need keep track of the minimum. We could have a global minimum value, however, it has a problem when the stack with the value popped. Then, we need to update the global min value which may take O(n) operation.

In the code below, each stack gets its own min-value the time when it was pushed by comparing the minimum of the previous top stack. When the top stack popped, the code checks if the top stack’s minimum value is the global min.

In summary, this code will get the stacks minimum value by peeking the top only, using peekMin() which returns the min-value for the top stack.

#include

using namespace std;

#define MIN(a,b) (a < b ? a : b)

class Stack

public:

Stack();

~Stack();

void push(int);

int pop();

int peek();

int peekMin();

friend void print(Stack&);

private:

typedef struct node

node *next;

int data;

int min;

NODE;

NODE *top;

;

Stack::Stack()

top = NULL;

Stack::~Stack()

while(top)

NODE *tmp = top;

top = top->next;

delete tmp;

void Stack::push(int n)

NODE *ptr = new NODE;

ptr->next = top;

ptr->data = n;

// currently empty (top is NULL)

if(top == NULL)

ptr->min = n;

else

ptr->min = MIN(n, top->min);

top = ptr;

int Stack::pop()

NODE *tmp = top;

int val = top->data;

top = top->next;

delete tmp;

cout << “pop ” << val << endl;

return val;

int Stack::peek()

return top->data;

int Stack::peekMin()

return top->min;

void print(Stack &s;)

Stack::NODE *cur = s.top;

while(cur)

cout << cur->data << ” “;

cur = cur->next;

cout << endl;

int main()

Stack *st = new Stack;

st->push(40);

st->push(50);

st->push(20);

st->push(10);

st->push(30);

print(*st);

cout << “minimum = ” << st->peekMin() << endl;

st->pop();

cout << “minimum = ” << st->peekMin() << endl;

st->pop();

cout << “minimum = ” << st->peekMin() << endl;

st->pop();

cout << “minimum = ” << st->peekMin() << endl;

st->pop();

cout << “minimum = ” << st->peekMin() << endl;

print(*st);

cout << “current top=” << st->peek();

return 0;

Output:

30 10 20 50 40

minimum = 10

pop 30

minimum = 10

pop 10

minimum = 20

pop 20

minimum = 40

pop 50

minimum = 40

40

current top=40

Example 7D – Stack Class Using Linked List with Query for Minimum Value (additional stack)

Even though the code in Example 7C can keep track of the minimum of the stack, it is obvious that the code is wasting resources. Suppose, we push the element with the minimum first: 10, 20, 30, 40 … with increasing order. In that case, the every stack element has additional thành viên for minimum value of 10. However, if we have separate stack just for minimum, we end up having only one stack because we do not save the values which are greater than the min-value.

Here is the code using separate stack (StackWithMin class) just for the minimum value.

#include

using namespace std;

typedef struct node

node *next;

int data;

NODE;

class Stack

public:

Stack();

virtual ~Stack();

virtual void push(int);

virtual int pop();

virtual int peekMin();

int peek();

friend void print(Stack&);

private:

bool empty();

NODE *top;

;

Stack::Stack()

top = NULL;

Stack::~Stack()

while(top)

NODE *tmp = top;

top = top->next;

delete tmp;

void Stack::push(int n)

NODE *ptr = new NODE;

ptr->next = top;

ptr->data = n;

top = ptr;

int Stack::pop()

NODE *tmp = top;

if(!empty())

int val = top->data;

top = top->next;

delete tmp;

cout << “pop ” << val << endl;

return val;

else

cout << “empty! ” << endl;

return -1;

int Stack::peek()

if(!empty()) return top->data;

return -1;

bool Stack::empty()

if(top == NULL) return true;

return false;

int Stack::peekMin()

return -1;

void print(Stack &s;)

NODE *cur = s.top;

while(cur)

cout << cur->data << ” “;

cur = cur->next;

cout << endl;

class StackWithMin : public Stack

public:

StackWithMin();

~StackWithMin();

void push(int);

int pop();

int peekMin();

private:

bool empty();

NODE* top;

;

StackWithMin::StackWithMin()

top = NULL;

StackWithMin::~StackWithMin()

while(top)

NODE *tmp = top;

top = top->next;

delete tmp;

void StackWithMin::push(int n)

if(top)

// push only if it’s smaller than the top min

if(n < top->data)

NODE *ptr = new NODE;

ptr->next = top;

ptr->data = n;

top = ptr;

// if empty, just push the new element

else

NODE *ptr = new NODE;

ptr->next = top;

ptr->data = n;

top = ptr;

Stack::push(n);

int StackWithMin::pop()

int popped = Stack::pop();

if(empty())

cout << “empty min stack” << endl;

return -1;

if(popped == top->data)

NODE *tmp = top;

if(top->next)

top = top->next;

else

top = NULL;

delete tmp;

return popped;

int StackWithMin::peekMin()

if(!empty()) return top->data;

cout << “empty min stack!” << endl;

return -1;

bool StackWithMin::empty()

if(top == NULL) return true;

return false;

int main()

Stack *st = new StackWithMin;

st->push(40);

st->push(50);

st->push(20);

st->push(10);

st->push(30);

print(*st);

cout << “minimum = ” << st->peekMin() << endl;

st->pop();

cout << “minimum = ” << st->peekMin() << endl;

st->pop();

cout << “minimum = ” << st->peekMin() << endl;

st->pop();

cout << “minimum = ” << st->peekMin() << endl;

st->pop();

cout << “minimum = ” << st->peekMin() << endl;

st->pop();

cout << “minimum = ” << st->peekMin() << endl;

print(*st);

cout << “current top=” << st->peek();

return 0;

Output:

30 10 20 50 40

minimum = 10

pop 30

minimum = 10

pop 10

minimum = 20

pop 20

minimum = 40

pop 50

minimum = 40

pop 40

empty min stack!

minimum = -1

Example 8 Queue Struct : Using Linked List

#include

#include

struct node

int data;

node *next;

;

typedef struct node node_t;

node_t *head = NULL;

void push(int n)

node_t *newNode = (node_t *)malloc(sizeof(node_t));

newNode->data = n;

newNode->next = NULL;

if(head == NULL)

head = newNode;

return;

node_t *cur = head;

while(cur)

if(cur->next==NULL)

cur->next = newNode;

return;

cur = cur->next;

void pop()

if(head==NULL) return;

node_t *tmp = head;

head = head->next;

không lấy phí(tmp);

void display()

node_t *cur = head;

while(cur)

printf(“%3d”,cur->data);

cur = cur->next;

printf(“n”);

int main()

push(1);push(2);push(3);push(4);push(5);display();

pop();display();

pop();display();

pop();display();

pop();display();

pop();display();

return 0;

Output is:

1 2 3 4 5

2 3 4 5

3 4 5

4 5

5

Example 8B – Queue Class: Using Linked List

First one becomes head, so when it pops, head will be popped.

#include

using namespace std;

class Queue

public:

Queue();

~Queue();

void push(int);

int pop();

void print();

private:

typedef struct Node

Node *next;

int data;

NODE;

NODE* head;

;

Queue::Queue()

head = NULL;

Queue::~Queue()

if(head == NULL) return;

NODE *cur = head;

while(cur)

Node *ptr = cur;

cur = cur->next;

delete ptr;

void Queue::push(int n)

if(head == NULL)

head = new NODE;

head->data = n;

head->next = NULL;

return;

NODE *cur = head;

while(cur)

if(cur->next == NULL)

NODE *ptr = new NODE;

ptr->data = n;

ptr->next = NULL;

cur->next = ptr;

return;

cur = cur->next;

void Queue::print()

if(head==NULL) return;

Node *cur = head;

while(cur)

cout << cur->data << ” “;

cur = cur->next;

cout << endl;

int Queue::pop()

if(head == NULL)

cout << “empty estack!” << endl;

return NULL;

NODE *tmp = head;

int value = head->data;

if(head->next)

head = head->next;

// pop the last element (head)

else

delete tmp;

head = NULL;

cout << “pop: ” << value << endl;;

return value;

int main()

Queue *que = new Queue();

que->push(10);

que->push(20);

que->push(30);

que->push(40);

que->push(50);

que->print();

que->pop();que->print();

que->pop();que->print();

que->pop();que->print();

que->pop();que->print();

que->pop();que->print();

que->pop();que->print();

return 0;

Output:

10 20 30 40 50

pop: 10

20 30 40 50

pop: 20

30 40 50

pop: 30

40 50

pop: 40

50

pop: 50

Example 9 – Finding Intersection and Union of Two Linked List

The following code finds intersection/union of two linked list and puts it into a new linked list.

#include

using namespace std;

struct node

int data;

node *next;

;

void add(struct node **head, int n)

struct node *cur;

struct node *new_node = (struct node *)malloc(sizeof(struct node));

new_node->data = n;

new_node->next = NULL;

if(*head == NULL)

*head = new_node;

return;

cur = *head;

while(cur)

if(cur->next == NULL)

cur->next = new_node;

return;

cur = cur->next;

bool isDuplicate(struct node *head, int n)

struct node* cur = head;

while(cur)

if(cur->data == n) return true;

cur = cur->next;

return false;

struct node *getIntersection(struct node *headA, struct node *headB)

struct node *curA = headA;

struct node *curB = headB;

struct node *result = NULL;

if(curA == NULL

struct node *getUnion(struct node *headA, struct node *headB)

struct node *cur;

struct node *result = NULL;

if(headA == NULL && headB == NULL) return NULL;

cur = headA;

while(cur)

add(&result;, cur->data);

cur = cur->next;

cur = headB;

while(cur)

/* check if the new data is already there */

if(!isDuplicate(result, cur->data))

add(&result;, cur->data);

cur = cur->next;

return result;

void display(struct node *head)

if(head == NULL) return;

struct node *cur = head;

while(cur)

cout << cur->data << ‘ ‘;

cur = cur->next;

cout << endl;

int main()

struct node *myListA = NULL;

struct node *myListB = NULL;

struct node *intersectionList = NULL;

struct node *unionList = NULL;

add(&myListA;,10);

add(&myListA;,20);

add(&myListA;,30);

add(&myListA;,40);

add(&myListA;,50);

add(&myListA;,60);

add(&myListA;,70);

cout << “List A: “;

display(myListA);

add(&myListB;,10);

add(&myListB;,30);

add(&myListB;,50);

add(&myListB;,70);

add(&myListB;,90);

add(&myListB;,110);

add(&myListB;,130);

cout << “List B: “;

display(myListB);

cout << “Intersection of A and B: “;

intersectionList = getIntersection(myListA, myListB);

display(intersectionList);

cout << “Union of A and B: “;

unionList = getUnion(myListA, myListB);

display(unionList);

return 0;

Output is:

List A: 10 20 30 40 50 60 70

List B: 10 30 50 70 90 110 130

Intersection of A and B: 10 30 50 70

Union of A and B: 10 20 30 40 50 60 70 90 110 130

Example 10 – Another Example of Generic Linked List

The following example is another example of generic use of linked list. It will be used as a base for doubly linked list later.

#include

using namespace std;

template

class List

struct Node

T data;

Node *next;

Node(T d, Node *n = 0):data(d), next(n)

;

Node *head;

public:

List(Node *h = 0):head(h)

~List();

void insert(Node *loc, T d);

void push_back(T d);

void push_front(T d);

T pop_back();

T pop_front();

void erase(Node *loc);

void display();

Node *search(T d);

;

// destructor

template

List::~List()

Node *tmp;

while(head)

tmp = head;

head = head->next;

delete tmp;

// insert d before loc

template

void List::insert(Node *loc, T d)

Node *new_node = new Node(d,0);

if(!head)

head = new_node;

return;

if(loc == head)

push_front(d);

return;

Node *cur = head;

while(cur->next)

if(cur->next == loc)

new_node->next = cur->next;

cur->next = new_node;

return ;

cur = cur->next;

template

void List::push_back(T d)

Node *new_node = new Node(d,0);

if(!head)

head = new_node;

return;

Node *cur = head;

while(cur)

if(!cur->next)

cur->next = new_node;

return;

cur = cur->next;

template

void List::push_front(T d)

Node *new_node = new Node(d,0);

if(!head)

head = new_node;

return;

new_node->next = head;

head = new_node;

return;

template

T List::pop_back()

Node *cur = head;

while(cur)

if(!cur->next)

T data (cur->data);

delete cur;

head = NULL;

return data;

else

if(!cur->next->next)

T data (cur->next->data);

cur->next = NULL;

delete cur->next;

return data;

cur = cur->next;

return NULL;

template

T List::pop_front()

if(!head) return NULL;

Node *tmp = head;

T data (head->data);

if(head->next)

head = head->next;

delete tmp;

return data;

delete tmp;

head = NULL;

return data;

template

void List::erase(Node *loc)

if(loc == head)

Node *tmp = head;

head = head->next;

delete tmp;

return;

Node *cur = head;

while(cur)

if(cur->next == loc)

cur->next = loc->next;

delete loc;

cur = cur->next;

template

typename List::Node* List::search(T d)

if(!head) return NULL;

Node* cur = head;

while(cur)

if(cur->data == d) return cur;

cur = cur->next;

return NULL;

template

void List::display()

if(!head) return;

Node *cur = head;

while(cur)

cout << cur->data << ” ” << endl;

cur = cur->next;

cout << endl;

int main()

List *myList = new List(NULL);

cout << “push_back() 20, 30 40, 50nn”;

myList->push_back(20);

myList->push_back(30);

myList->push_back(40);

myList->push_back(50);

myList->display();

cout << “push_front() 10nn”;

myList->push_front(10);

myList->display();

cout << “erase 30nn”;

myList->erase(myList->search(30));

myList->display();

cout << “insert 30 before 40nn”;

myList->insert(myList->search(40),30);

myList->display();

cout << “pop_back()n”;

cout << myList->pop_back() << ” just back poppednn”;

myList->display();

cout << “pop_front()n”;

cout << myList->pop_front() << ” just front poppednn”;

myList->display();

return 0;

Output:

push_back() 20, 30 40, 50

20

30

40

50

push_front() 10

10

20

30

40

50

erase 30

10

20

40

50

insert 30 before 40

10

20

30

40

50

pop_back()

50 just back popped

10

20

30

40

pop_front()

10 just front popped

20

30

40

List of Linked List Examples of This Page

Example 1
When the head of the list is not a global pointer.

Example 2 and Example 3
When the head of the list is a global pointer.
There are some implementation differences between these two examples.

Example 4
Used class & structure in that class.

Example 5A
Detecting circular (loop) linked list.

Example 5B
Detecting circular (loop) linked list (Generic Class with Template).

Example 6
Stack with linked list data structure.

Example 7
Class Stack with linked list data structure.

Example 7B
Class Stack with linked list data structure.

Example 7C
Class Stack using linked list with query for minimum value.

Example 7D
Stack Class Using Linked List with Query for Minimum Value (additional stack).

Example 8
Queue Struct with linked list data structure.

Example 8B
Queue Class with linked list data structure.

Example 9
Finding intersection and union of two linked lists.

Example 10
Generic linked lists.

Also, there are set of linked list samples:

Reply

0

0

Chia sẻ

Chia Sẻ Link Download Linked list with two values C++ miễn phí

Bạn vừa Read tài liệu Với Một số hướng dẫn một cách rõ ràng hơn về Video Linked list with two values C++ tiên tiến và phát triển nhất và Chia SẻLink Download Linked list with two values C++ Free.

Giải đáp vướng mắc về Linked list with two values C++

Nếu sau khi đọc nội dung bài viết Linked list with two values C++ vẫn chưa hiểu thì hoàn toàn có thể lại phản hồi ở cuối bài để Mình lý giải và hướng dẫn lại nha

#Linked #list #values

Related posts: