Linked List using a Sentinel
Linked List.h
/*
* Linked List.h
* Using a sentinel for search
*
* Created by Enoch Hwang on 2/1/10.
* Copyright 2010 La Sierra University. All rights reserved.
*
*/
#include<iostream>
usingnamespace std;
class LinkedList{
private:
struct ListNode {
int data;
ListNode *next;
};
ListNode *head;
ListNode *tail;
public:
LinkedList();
void InsertNode(int d);
bool SearchNode(int d);
void PrintList();
bool DeleteNode(int d);
};
Linked List.cpp
#include"Linked List.h"
LinkedList::LinkedList(){// constructor
head = NULL;
tail = NULL;
}
void LinkedList::InsertNode(int d){
ListNode *np = new ListNode;// allocate memory for new node
np->data = d;// put data in new node
if(head == NULL){// empty list special case
head = np;// set head and tail pointers
tail = np;
np->next = NULL;
}else{
// search for correct location to insert node
// set up the sentinal first. This part is almost the same as the code in the Search routine
ListNode *sp = new ListNode;
sp->data = d;
sp->next = NULL;
tail->next = sp;
// do search
ListNode *p = head;// pointer for traversing the list
ListNode *pp = p;// previous pointer that follows p
while (p->data < d) {
pp = p;// update previous pointer
p = p->next;// move to next node
}
// remove the sentinal
tail->next = NULL;
delete sp;
// see where to insert the new node
if (p == head) {
// insert to head of list
np->next = head;
head = np;
} elseif (p == sp) {
// insert to tail of list
tail->next = np;
np->next = NULL;
tail = np;
} else {
// insert to middle of list
np->next = pp->next;
pp->next = np;
}
}
cout < " Node " < d < " inserted" < endl;
}
bool LinkedList::SearchNode(int d){
if (head == NULL)
returnfalse;// empty list
// set up the sentinal at the end of the list
ListNode *sp = new ListNode;
sp->data = d;
sp->next = NULL;
tail->next = sp;
// do search
ListNode *p = head;
while (p->data != d) {
p = p->next;// move to next node
}
// remove the sentinal
tail->next = NULL;
delete sp;// note that even though the memory is released, sp is still
// pointing at that location so the test below is still ok
// return node found or not found
if (p != sp)
returntrue;// found if p is not pointing at the sentinal
else
returnfalse;
}
void LinkedList::PrintList(){
ListNode *ptr = head;
cout < "Here's the linked list..." < endl;
while(ptr != NULL){
cout < " " < ptr->data;
ptr = ptr->next;
}
cout < endl < endl;
if (head == NULL) {
cout < "head is pointing to NULL" < endl;
cout < "tail is pointing to NULL" < endl;
cout < endl;
} else {
cout < "head is pointing to node " < head->data < endl;
cout < "tail is pointing to node " < tail->data < endl;
cout < endl;
}
}
bool LinkedList::DeleteNode(int d){
if (head == NULL) {
cout < " Did not find " < d < " to delete" < endl;
returnfalse;// empty list
}
// search for node to delete
// set up the sentinal first. This part is almost the same as the code in the Search routine
ListNode *sp = new ListNode;
sp->data = d;
sp->next = NULL;
tail->next = sp;
// do search
ListNode *p = head;// pointer for traversing the list
ListNode *pp = p;// previous pointer that follows p
while (p->data < d) {
pp = p;// update previous pointer
p = p->next;// move to next node
}
// remove the sentinal
tail->next = NULL;
delete sp;
if (p == sp) {
// node not found so no deletion
cout < " Did not find " < d < " to delete" < endl;
returnfalse;
}
// delete the node where p is pointing at
// see where the node is in the list
if (p == head) {
// delete the head
head = p->next;// remove node from the head of the list
delete p;// release the memory pointed to by p
} elseif (p == tail) {
// delete the tail
pp->next = NULL;
delete tail;
tail = pp;
} else {
// delete the middle
pp->next = p->next;
delete p;
}
cout < " Node " < d < " deleted" < endl;
returntrue;
}
main.cpp
/*
* This program demonstrates the creation of a linked list with a sentinal for search
*
* Created by Enoch Hwang on 2/1/10.
* Copyright 2010 La Sierra University. All rights reserved.
*/
#include<iostream>
#include"Linked List.h"
usingnamespace std;
void main (int argc, char * const argv[]) {
LinkedList L;// create an empty list
int n, select;
while (1) {
cout < "1 = insert" < endl;
cout < "2 = search" < endl;
cout < "3 = delete" < endl;
cout < "4 = print list" < endl;
cout < "0 = end" < endl;
cout < "? ";
cin > select;
cout < endl;
switch (select) {
case 1:
cout < "Enter number to insert? ";
cin > n;
L.InsertNode(n);
break;
case 2:
cout < "Enter number to search? ";
cin > n;
if(L.SearchNode(n) == true)
cout < " " < n < " is found in the list" < endl;
else
cout < " " < n < " is NOT found in the list" < endl;
break;
case 3:
cout < "Enter number to delete? ";
cin > n;
L.DeleteNode(n);
break;
case 4:
cout < "Linked list..." < endl;
L.PrintList();
break;
default:
exit (1);
}
cout < endl;
}
}