Objective:
To implement Linked List ADT functions.
Description:
Arrays
are used to save data in memory as long as program runs, our program can
read/write data to arrays. Some pluses and minuses of arrays are
+ Fast element access.
--
Impossible to resize.
•
Many
applications require resizing!
•
Required
size not always immediately available.
To
overcome the Plus & minuses of arrays, Solution was proposed in form of
Linked lists. Linked lists are type of data structure that provide Resize
ability at run time with small computational complexity as compared to dynamic
arrays.
Linked List:
Linked
List is a collection of data in which each element contains the location of the
next element.
- Each element contains two parts: data and link.
- The link contains a pointer
(an address) that identifies the next element in the list.
Both an
array and a linked list are representations of a list of items in memory. The
only difference is the way in which the items are linked together. Figure
compares the two representations for a list of five integers.
Nodes: Nodes are
the basic building elements in a linked list. The nodes in a linked list are
called self-referential records because each instance of the record contains a
pointer to another instance of the same structural type.
Basic Operations in linked list ADT:
1. 1. Insertion
(Start, End, Any position)
2. 2. Deletion
(Start, End, Any position)
3. 3. Searching
or Iterating through the list to display items.
Inserting at the start
- Allocate a new node
- Insert new element
- Make new node point to old head
- Update head to point to new node.
Inserting at any position
1. Allocate a new node
2. Insert new element.
3. Access address of previous node from the position you want to insert and address of current node (position node).
2.
Pass the address of the current node in the next
field of the new node.
We will access these nodes by asking the user at what
position he wants to insert the new node. Now, we will start a loop to reach
those specific nodes. We initialized our current node by the head and move
through the linked list. At the end, we would find two consecutive nodes.
Delete at the start
1 Update
head to point to next node in the list
2.
Allow
garbage collector to reclaim the former first node
3.
De
allocate the first node.
hd
Delete at the end:
Make two temporary pointers (previous and current) and find nodes that comes before the last node.
2.
Previous node will point to the second to the
last node and the current node will point to the last node, i.e., node to be
deleted.
3.
Delete current node and make the previous node
as the tail.
hs
Delete at any position
1. Make two temporary pointers (previous and current) and traverse until find specific node which need to be deleted. Delete respective node and pass the address of the node after it to the previous node.
1. Create template Linked List ADT and provide
a. Constructor / copy constructor
b. Destructor
c. InsertAtStart(intval)
d. InsertAtAnyposition(intposition,intval)
e. insertAtEnd(intval)
f.
deleteAtstart()
g. DeleteAtAnyposition(node)
h. deleteAtEnd()
i.
Traverse()
j.
isEmpty()
Note: Your program should have no memory leakage & dangling pointers. Your program should be validated properly and display warnings and errors to user as well. Reuse functions if needed to increase program efficiency.
|
#include <iostream> using namespace std;
struct node { int data; node* next; };
class LinkedList { public: node* head;
LinkedList() { head = NULL; }
bool isEmpty() { if (head == NULL) { return true; } else return false; }
void iAs(int data) { node* s = new node; (*s).data = data; (*s).next = NULL; if (head == NULL) { head = s; } else { (*s).next =
head; head = s; } } void iAAp(int pos,int data) { if (pos == 1) { iAs(data); } else { node* p = new node; (*p).data = data; (*p).next = NULL; node* temp = head; for (int i = 1; i < pos - 1; i++) { temp =
(*temp).next; } (*p).next =
(*temp).next;
(*temp).next=p;
} } void iAe(int data) { node* e = new node; (*e).data = data; (*e).next = NULL;
if (head == NULL) { head = e; } else { node* temp; temp = head; while ((*temp).next != NULL) { temp =
(*temp).next; } (*temp).next =
e; } }
void dAs() { node* temp = new node; temp = head; head =
(*head).next; delete temp; }
void dAAp(int nodepos) { if (isEmpty()) { cout << "The
list is Empty....!!!!!"; } if (nodepos == 1) { dAs(); } else { node* temp1, * temp2; temp1 = head;
for (int i = 1; i < nodepos - 1; i++) { temp1 =
(*temp1).next; }
temp2 =
(*temp1).next; (*temp1).next
= (*temp2).next; delete temp2;
}
}
void dAe() { node* temp = head; node* temp2 = (*temp).next; while ((*temp2).next != NULL) { temp =
(*temp).next; temp2 =
(*temp2).next; }
delete temp2; (*temp).next = NULL; } void Traverse() { if (isEmpty()) { cout << "The
list is Empty....!!!!!"; } else { node* n = head; while (n != NULL) { cout << (*n).data << "
"; n =
(*n).next; } cout << endl; } }
LinkedList(const LinkedList &a) { head = a.head; if (isEmpty()) { head = NULL; } else { node* temp = head; node* n = new node; (*n).data =
(*temp).data; head = n; (*temp).next =
(*head).next; node* temp2 = head;
while (temp != NULL) { node* b = new node;
(*temp2).next = b;
(*temp2).data = (*temp).data; temp =
(*temp).next; temp2 =
(*temp2).next;
} (*temp2).next
= NULL; } }
~LinkedList() { if (isEmpty()) { head = NULL; } else { node* temp1, * temp2; temp1 = head; temp2 =
(*temp1).next; while (temp2!=NULL) { delete temp1; temp1 =
temp2; temp2 =
(*temp2).next; } head = NULL; } } };
int main()
{ LinkedList MyList; LinkedList MyList2(MyList); cout << MyList.isEmpty() << endl; for (int i = 1; i <= 5; i++) { MyList.iAAp(i, i); } cout << MyList.isEmpty() << endl; MyList.Traverse(); MyList.dAs(); MyList.Traverse(); MyList.iAs(6); MyList.Traverse(); MyList.iAe(9); MyList.Traverse(); MyList.dAe(); MyList.Traverse(); MyList.dAAp(3); MyList.Traverse(); MyList.iAAp(4, 7); MyList.Traverse(); MyList.dAs(); MyList.Traverse(); MyList.dAAp(2); MyList.Traverse(); MyList.dAs(); MyList.dAs(); MyList.dAs(); MyList.Traverse();
}
|
Output:
No comments:
Post a Comment