Linked List ADT (.cpp)int IntSLList::deleteFromHead() {
int el = head->info;
IntNode *tmp = head;
if (head == tail) // if only one node on the // list;
head = tail = 0;
else head = head->next;
delete tmp;
return el;
}
IntNode Class
info next class IntNode {
public:
int info;
class IntNode *next;
IntNode(int el, IntNode *ptr = 0) {
info = el; next = ptr;
}
};
diagrammatic representation:
* Material presented here is taken mostly from Drozdek’s book, “Data Structures and Algorithms in C++”
IntNode Class
10 p 10 p 8 IntNode *p = new IntNode(10);
p->info == 10; p->next == 0; after the statement is executed
p->next = new IntNode(8);
IntNode Class
p->next->next = new IntNode(50);
See if you can draw the resulting diagram.
Exercise. Draw a diagram to illustrate the configuration of linked nodes that is created by the following statements.
IntNode *p0 = new IntNode(3);
IntNode *p1 = p0->next = new IntNode(5);
IntNode *p2 = p1->next = new IntNode(9);
Exercise. Write the C++ statements that are needed to created the configurations (to be drawn on the blackboard)
Exercise diagram
Linked List (non-OO)
How to create a list (1, 3, 5, 6, 7, 9)?
Draw a series of diagrams first
Linked List ADT (.h)
class IntSList {
public:
IntSLList() { head = tail = 0; }
~IntSLList();
int isEmpty() { return head == 0; }
void addToHead(int);
void addToTail(int);
int deleteFromHead(); // delete the head and // return its info;
int deleteFromTail(); // delete the tail and // return its info;
void deleteNode(int);
bool isInList(int) const;
void printAll() const;
private:
IntNode *head, *tail;
};
Linked List ADT (.cpp)
#include
using std::cout;
#include "intSLLst.h"
IntSLList::~IntSLList() {
for (IntNode *p; !isEmpty(); ) {
p = head->next;
delete head;
head = p;
}
}
Linked List ADT (.cpp)
void IntSLList::addToHead(int el) {
head = new IntNode(el,head);
if (tail == 0)
tail = head;
}
void IntSLList::addToTail(int el) {
if (tail != 0) { // if list not empty;
tail->next = new IntNode(el);
tail = tail->next;
}
else head = tail = new IntNode(el);
}
Linked List ADT (.cpp)
int IntSLList::deleteFromHead() {
int el = head->info;
IntNode *tmp = head;
if (head == tail) // if only one node on the // list;
head = tail = 0;
else head = head->next;
delete tmp;
return el;
}
Linked List ADT (.cpp)
int IntSLList::deleteFromTail() {
int el = tail->info;
if (head == tail) { // if only one node on the list;
delete head;
head = tail = 0;
}
else { // if more than one node in the // list,
IntNode *tmp; // find the predecessor of tail;
for (tmp = head; tmp->next != tail;
tmp = tmp->next);
delete tail;
tail = tmp; // the predecessor of tail // becomes tail;
tail->next = 0;
}
return el;
}
Linked List ADT (.cpp)
void IntSLList::deleteNode(int el) {
if (head != 0) // if non-empty list;
if (head == tail && el == head->info) {
// if only one node on the list;
delete head;
head = tail = 0;
}
else if (el == head->info) {
// if more than one node on the list
IntNode *tmp = head;
head = head->next;
delete tmp; // and old head is deleted;
}
else { // if more than one node in the list
IntNode *pred, *tmp;
Linked List ADT (.cpp)
// and a non-head node is deleted;
for (pred = head, tmp = head->next;
tmp != 0 && !(tmp->info == el);
pred = pred->next, tmp =
tmp->next);
if (tmp != 0) {
pred->next = tmp->next;
if (tmp == tail)
tail = pred;
delete tmp;
}
}
}
info next prev class IntNode {
public:
int info;
class IntNode *next, *Prev;
IntNode(int el, IntNode *ptrn = 0,
IntNode *ptrp = 0) {
info = el; next = ptrn; prev = ptrp;
}
};
diagrammatic representation:
Stack
First-in, Last-out (FILO)
Can be implemented with array or linked list
Has many applications
Queue
First-in, First-out (FIFO)
Can be implemented with array or linked list
Has many applications
Comments