Created
August 5, 2016 17:00
-
-
Save tareq-si-salem/0311ed4f3b96c35184fa7f2bae69465f to your computer and use it in GitHub Desktop.
Linked List and Array List Implementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <cstdio> | |
using namespace std; | |
const int MAX = 10; | |
// MAX specifies the maximum size the list can take | |
// in the array case. | |
// compares two strings according to Alphabetical order | |
// if a string is greater than the other returns 1 | |
// if less return -1 | |
// otherwise 0 | |
// if a string is a substring of the other | |
// the largest is greater so: | |
// aaaa > aaa > aa > a | |
// a > b and a == a | |
// ab < aa and aa = aa | |
// .. | |
int str_compare(char *a, char *b) { | |
int i = 0; | |
while (true) { | |
if (a[i] == '\0' && b[i] == '\0') { | |
return 0; | |
} else if (b[i] == '\0' || a[i] > b[i]) { | |
return 1; | |
} else if (a[i] == '\0' || a[i] < b[i]) { | |
return -1; | |
} else i++; | |
} | |
} | |
namespace PartA { | |
// we used separate name spaces | |
// for array and pointer implementation | |
typedef struct List { | |
char *names[MAX]; | |
// a string field to hold names. | |
int size; | |
// size of the List must not exceed MAX; | |
// usually with array lists (Like in Java) it has a capacity variable | |
// that increases whenever the list is near to be full | |
// and copies old data to a new array with a larger capacity | |
} List; | |
// list is passed by reference | |
// so a change that happens within the function | |
// changes the list (not its copy) | |
int init(List &l) { | |
l.size = 0; | |
// initialize the list by setting size to 0 | |
// the list is initially empty | |
} | |
// inserts a name:"string" at position p | |
// With few constrains | |
// p should be between 0 and list size otherwise p is out of range | |
// The name added should be less or equal names[p] and if p not equal to 0 | |
// name must be greater or equal to names[p-1] | |
// otherwise adding the name will make the list unordered | |
void insert(List &list, int p, char *name) { | |
if (list.size < MAX) { | |
if (p <= list.size && p >= 0) { | |
if (list.size == 0 && p == 0) { | |
list.names[0] = name; | |
list.size++; | |
} else if (p == list.size && str_compare(name, list.names[p - 1]) >= 0) { | |
list.names[list.size] = name; | |
list.size++; | |
} else { | |
if ((p == 0 && str_compare(name, list.names[p]) <= 0) || (str_compare(name, list.names[p]) <= 0 && str_compare(name, | |
list.names[p - 1]) >= 0) | |
) { | |
for (int i = list.size; i >= p; i--) | |
list.names[i + 1] = list.names[i]; | |
// shift names to the right of the list starting from p to | |
// list size | |
list.names[p] = name; | |
list.size++; | |
// a name element is added so the list size is increased | |
} else { | |
cout << "Cannot insert a new name to maintain the list order" << endl; | |
} | |
} | |
} else { | |
cout << "Position is out of list range" << endl; | |
} | |
} else { | |
cout << "List is full can't add more elements" << endl; | |
} | |
} | |
// remove an element from the list if it's | |
// between the start of the list and its end | |
// otherwise we can't delete an element that's not in the list | |
// | |
void remove(List &list, int p) { | |
if (p < list.size && p >= 0) { | |
for (int i = p; i < list.size - 1; i++) | |
list.names[i] = list.names[i + 1]; | |
// shift the list to the left until p | |
list.size--; | |
// and decrement size because name | |
// at position p is deleted | |
} else { | |
cout << "Position is out of list range" << endl; | |
} | |
} | |
// a simple linear search to stop when | |
// we find an occurrence of name in the list | |
// returns it's index in the list | |
// if not found returns -1 | |
int find(List &list, char* name) { | |
for (int i = 0; i < list.size; i++) { | |
if (str_compare(list.names[i], name) == 0) { | |
return i; | |
} | |
} | |
return -1; | |
} | |
// print the list in increasing order | |
void traverseForward(List list) { | |
if (list.size != 0) { | |
cout << "List(forward): [ "; | |
for (int i = 0; i < list.size; i++) { | |
cout << list.names[i] << " "; | |
} | |
cout << "]" << endl; | |
} else { | |
cout << "List is empty" << endl; | |
} | |
} | |
// print the list in decreasing order | |
void traverseBackward(List list) { | |
if (list.size != 0) { | |
cout << "List(backward): [ "; | |
for (int i = list.size - 1; i >= 0; i--) { | |
cout << list.names[i] << " "; | |
} | |
cout << "]" << endl; | |
} else { | |
cout << "List is empty" << endl; | |
} | |
} | |
} | |
namespace PartB { | |
// the name space of part B pointer implementation | |
struct ListItem { | |
char *name; | |
// a string field to represent cell value. | |
ListItem *next; | |
// a pointer to the next cell (to be linked to) | |
}; | |
typedef ListItem* LinkedList; | |
// defining a linked list (pointer to cells) | |
int init(LinkedList &list) { | |
list = NULL; | |
} | |
// initially the list is empty | |
// so it points to NULL (no cell) | |
// Same as in the array implementation we have to respect the same conditions | |
void insert(LinkedList &list, int p, char *name) { | |
if (p == 0) { | |
if (list == NULL || str_compare(name, list->name) <= 0) { | |
// if the cell is added to the head of the list | |
// we only need to check if the new cell | |
// has a name less or equal to the current head cell name | |
// if the list is empty we don't need to compare | |
LinkedList item = new ListItem; | |
item->name = name; | |
item->next = list; | |
list = item; | |
} else { | |
cout << "Cannot insert a new name to maintain the list order" << endl; | |
} | |
} else { | |
LinkedList temp = list; | |
// create a new pointer temp to not change the original list | |
int count = 0; | |
// count to keep track of the current position in the list | |
while (count < p - 1 && temp != NULL) { | |
// if current position is less than p - 1 stop the loop | |
// or stop it when temp == NULL (end of the list) | |
temp = temp->next; | |
// next cell is assigned to current cell | |
// traverse the list | |
count++; | |
} | |
if (temp != NULL) { | |
if (temp->next == NULL && str_compare(name, temp->name) >= 0 || | |
// if it's the tail of the list | |
// just compare with the old tail cell | |
(str_compare(name, temp->name) >= 0 | |
&& str_compare(name, temp->next->name) <= 0) | |
// if not the tail nor the head cell of the list | |
// we need to compare with cellp and cellp+1 | |
) { | |
LinkedList item = new ListItem; | |
item->name = name; | |
item->next = temp->next; | |
temp->next = item; | |
// old list cellp-1 -> cellp ->cellp+1 | |
// new list cellp-1 -> newcell -> cellp->cellp+1 | |
} else { | |
cout << "Cannot insert a new name to maintain the list order" << endl; | |
} | |
} else { | |
cout << "position out of list range" << endl; | |
} | |
} | |
} | |
// delete a cell from the list | |
// | |
void remove(LinkedList &list, int p) { | |
LinkedList temp = list; | |
int count = 0; | |
if (list != NULL) { | |
if (p == 0) { | |
LinkedList temp2 = temp; | |
temp = temp->next; | |
delete temp2; | |
} else { | |
while (count < p - 1 && temp != NULL) { | |
temp = temp->next; | |
count++; | |
} | |
if (temp != NULL) { | |
LinkedList temp2 = temp->next; | |
temp->next = temp2->next; | |
delete temp2; | |
} else { | |
cout << "position out of list range" << endl; | |
} | |
} | |
} else { | |
cout << "The list is empty" << endl; | |
} | |
} | |
//print the content of the list in increasing order | |
void traverseForward(LinkedList list) { | |
if (list != NULL) { | |
cout << "List (forward)[ "; | |
while (list != NULL) { | |
cout << list->name << " "; | |
list = list->next; | |
} | |
cout << "]" << endl; | |
} else { | |
cout << "The list is empty" << endl; | |
} | |
} | |
// needed to print the list in backward | |
// because the cout statement isn't reached until | |
// the tail of the list is reached | |
// then it prints the list in reverse | |
void traverse_recursive(LinkedList list) { | |
if (list != NULL) { | |
traverse_recursive(list->next); | |
cout << list->name << " "; | |
} | |
} | |
// calls the recursive traverse | |
void traverseBackward(LinkedList list) { | |
if (list != NULL) { | |
cout << "List (backward)[ "; | |
traverse_recursive(list); | |
cout << "]" << endl; | |
} else { | |
cout << "The list is empty" << endl; | |
} | |
} | |
// a simple linear search to stop when | |
// we find an occurrence of name in the list | |
// returns it's index in the list | |
// if not found returns -1 | |
int find(LinkedList list, char* name) { | |
int count = 0; | |
while (list != NULL) { | |
if (str_compare(name, list->name) == 0) | |
return count; | |
else | |
count++; | |
list = list->next; | |
} | |
// if the list end reached | |
// implies no occurrence of name was | |
// found in the list | |
if (list == NULL) | |
return -1; | |
} | |
} | |
int main() { | |
cout << "Where do you want to store names ?" << endl; | |
cout << "1. Array list " << endl; | |
cout << "2. Linked list" << endl; | |
char optionI, optionII; | |
char *name; | |
int p, index; | |
bool loop = true; | |
PartA::List arrayList; | |
PartA::init(arrayList); | |
PartB::LinkedList linkedList; | |
PartB::init(linkedList); | |
cout << "option: "; | |
cin >> optionI; | |
cout << "1. insert new item" << endl; | |
cout << "2. delete an item" << endl; | |
cout << "3. find an item" << endl; | |
cout << "4. print the list in increasing order" << endl; | |
cout << "5. print the list in decreasing order" << endl; | |
cout << "q. to exit" << endl; | |
while (loop) { | |
cout << "Select option: "; | |
cin >> optionII; | |
cin.ignore(); | |
name = new char[10]; | |
if (optionI == '1') { | |
switch (optionII) { | |
case '1': | |
cout << "Enter name: "; | |
cin.getline(name, 10); | |
cout << "Enter position: "; | |
cin >> p; | |
PartA::insert(arrayList, p, name); | |
break; | |
case '2': | |
cout << "Enter position: "; | |
cin >> p; | |
PartA::remove(arrayList, p); | |
break; | |
case '3': | |
cout << "Enter name to find: "; | |
cin.getline(name, 10); | |
index = PartA::find(arrayList, name); | |
if (index != -1) { | |
cout << "name found at: " << index << endl; | |
} else { | |
cout << "name not found" << endl; | |
} | |
break; | |
case '4': | |
PartA::traverseForward(arrayList); | |
break; | |
case '5': | |
PartA::traverseBackward(arrayList); | |
break; | |
case 'q': | |
loop = false; | |
break; | |
} | |
} else { | |
switch (optionII) { | |
case '1': | |
cout << "Enter name: "; | |
cin.getline(name, 10); | |
cout << "Enter position: "; | |
cin >> p; | |
PartB::insert(linkedList, p, name); | |
break; | |
case '2': | |
cout << "Enter position: "; | |
cin >> p; | |
PartB::remove(linkedList, p); | |
break; | |
case '3': | |
cout << "Enter name to find: "; | |
cin.getline(name, 10); | |
index = PartB::find(linkedList, name); | |
if (index != -1) { | |
cout << "name found at: " << index << endl; | |
} else { | |
cout << "name not found" << endl; | |
} | |
break; | |
case '4': | |
PartB::traverseForward(linkedList); | |
break; | |
case '5': | |
PartB::traverseBackward(linkedList); | |
break; | |
case 'q': | |
loop = false; | |
break; | |
} | |
} | |
cout << "------------------------" << endl; | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment