Linked Lists Implementation Method 2 (1).ppt

The document provides an overview of linked lists, a linear data structure used to store collections of elements where each element is represented by a node

1. Data Structures & Algorithms
Linked List Implementation

2. Data Structures & Algorithms
Linked Lists
•Node data
–Data for each node
–Link to next node
•Start pointer
•How to implement a Linked List structure using
a class?
Suggestions??

3. Data Structures & Algorithms
Linked List Class
•Depends upon requirement
–Do we need to create only one list or more lists?
–If only one list is desired then simply make
•start pointer as static (only one start pointer required)
•data members and link to next node (next pointer) as non static
–If number of lists desired are more than one then start pointer
required for each list
•Creating struct for each node
•And making a list class
–We will see implementation of linked list by both methods

4. Data Structures & Algorithms
First Method: Declaring start pointer as static
1.class IntList
2.{
3. static IntList *ListHeadPtr;
4. int data;
5. IntList *next;
6.public:
7. static void AddNodeAtHead(int val);
8. static void AddNodeAtTail(int val);
9. static void DisplayList(void);
10. static void DeleteNode(int key);
11. static void DisplaySpecificNode( int key);
12.};
13.//defining and initializing static member of class
14.IntList* IntList::ListHeadPtr=NULL;

5. Data Structures & Algorithms
1.void IntList::AddNodeAtHead( int val)
2.{
3. IntList *ptrNew = new IntList;
4. ptrNew->data = val;
5. ptrNew -> next = ListHeadPtr;
6. ListHeadPtr = ptrNew;
7.}
8.void IntList::AddNodeAtTail( int val)
9.{
10. IntList *ptrNew = new IntList, *ptrTemp=ListHeadPtr;
11. ptrNew->data = val;
12. ptrNew -> next = NULL;
13. if (ListHeadPtr == NULL)
14. {
15. ListHeadPtr = ptrNew;
16. return;
17. }
18. while (ptrTemp->next!=NULL)
19. ptrTemp=ptrTemp->next;
20. ptrTemp->next= ptrNew;
21.}

6. Data Structures & Algorithms
1.void IntList::DisplayList( void)
2.{
3. IntList *ptrTemp=ListHeadPtr;
4. cout<<endl;
5. while (ptrTemp!=NULL)
6. {
7. cout<<ptrTemp->data<<",";
8. ptrTemp=ptrTemp->next;
9. }
10.}
11.void IntList::DisplaySpecificNode( int key)
12.{
13. IntList *ptrCurrent=ListHeadPtr;
14. while (ptrCurrent!=NULL && ptrCurrent->data!=key)
15. ptrCurrent = ptrCurrent->next;
16. if (ptrCurrent == NULL)
17. cout<<"\nElement not found in the list";
18. else
19. cout<<"\nData for node is :"<<ptrCurrent->data;
20.}

7. Data Structures & Algorithms
1.void IntList::DeleteNode( int key)
2.{
3. IntList *ptrCurrent=ListHeadPtr,*ptrPrevious;
4. while (ptrCurrent!=NULL && ptrCurrent->data!=key)
5. {
6. ptrPrevious = ptrCurrent;
7. ptrCurrent = ptrCurrent->next;
8. }
9. if (ptrCurrent == NULL)
10. {
11. cout<<"\nElement to delete not found in the list";
12. return;
13. }
14. if (ptrCurrent == ListHeadPtr) //node to delete is first node
15. ListHeadPtr = ListHeadPtr->next;
16. else //node to delete is in middle or at end of list
17. ptrPrevious->next = ptrCurrent->next;
18. delete ptrCurrent;
19.}

8. Data Structures & Algorithms
1.void main(void)
2.{
3. IntList::AddNodeAtTail(20);
4. IntList::AddNodeAtHead(10);
5. IntList::AddNodeAtHead(34);
6. IntList::AddNodeAtTail(12);
7. IntList::DisplayList();
8. IntList::DeleteNode(30);
9. IntList::DisplayList();
10.}

9. Data Structures & Algorithms
Destructor of list
•Do we need to write a destructor which should delete all nodes
of linked list?
•Obviously No!!!!!!
•For destroying whole list we should define another static
member function, DeleteAll

10. Data Structures & Algorithms
Second Method: Using struct for node data
1.class IntList
2.{
3. struct Node
4. {
5. int data;
6. Node *next;
7. };
8. Node *ListHeadPtr;
9.public:
10. IntList() { ListHeadPtr = NULL; }
11. void AddNodeAtHead(int val);
12. void AddNodeAtTail(int val);
13. void DisplayList(void);
14. void DeleteNode(int key);
15. void DisplaySpecificNode( int key);
16. ~IntList();
17.};

11. Data Structures & Algorithms
1.void IntList::AddNodeAtHead( int val)
2.{
3. Node *ptrNew = new Node;
4. ptrNew->data = val;
5. ptrNew -> next = ListHeadPtr;
6. ListHeadPtr = ptrNew;
7.}
8.void IntList::AddNodeAtTail( int val)
9.{
10. Node *ptrNew = new Node, *ptrTemp=ListHeadPtr;
11. ptrNew->data = val;
12. ptrNew -> next = NULL;
13. if (ListHeadPtr == NULL)
14. {
15. ListHeadPtr = ptrNew;
16. return;
17. }
18. while (ptrTemp->next!=NULL)
19. ptrTemp=ptrTemp->next;
20. ptrTemp->next= ptrNew;
21.}

12. Data Structures & Algorithms
1.void IntList::DisplayList( void)
2.{
3. Node *ptrTemp=ListHeadPtr;
4. cout<<endl;
5. while (ptrTemp!=NULL)
6. {
7. cout<<ptrTemp->data<<",";
8. ptrTemp=ptrTemp->next;
9. }
10.}
11.void IntList::DisplaySpecificNode( int key)
12.{
13. Node *ptrCurrent=ListHeadPtr;
14. while (ptrCurrent!=NULL && ptrCurrent->data!
=key)
15. ptrCurrent = ptrCurrent->next;
16. if (ptrCurrent == NULL)
17. cout<<"\nElement not found in the list";
18. else
19. cout<<"\nData for node is :"<<ptrCurrent->data;
20.}

13. Data Structures & Algorithms
1.void IntList::DeleteNode( int key)
2.{
3. Node *ptrCurrent=ListHeadPtr,*ptrPrevious;
4. while (ptrCurrent!=NULL && ptrCurrent->data!=key)
5. {
6. ptrPrevious = ptrCurrent;
7. ptrCurrent = ptrCurrent->next;
8. }
9. if (ptrCurrent == NULL)
10. {
11. cout<<"\nElement to delete not found in the list";
12. return;
13. }
14. if (ptrCurrent == ListHeadPtr) //node to delete is
first node
15. ListHeadPtr = ListHeadPtr->next;
16. else //node to delete is in middle or at end of list
17. ptrPrevious->next = ptrCurrent->next;
18. delete ptrCurrent;
19.}

14. Data Structures & Algorithms
1.IntList::~IntList()
2.{
3. Node *ptrPrevious;
4. while (ListHeadPtr!=NULL)
5. {
6. ptrPrevious = ListHeadPtr;
7. ListHeadPtr= ListHeadPtr->next;
8. delete ptrPrevious;
9. }
10.}

15. Data Structures & Algorithms
1./*Driver program. Number of calls to functions of class
to test working, you should call more functions, and
look results thoroughly*/
2.void main(int key)
3.{
4. IntList list1,list2;
5. list1.AddNodeAtTail(20);
6. list1.AddNodeAtHead(10);
7. list1.AddNodeAtHead(34);
8. list1.AddNodeAtTail(12);
9. list1.DeleteNode(10);
10. cout<<"\nList1 after perorming few operations:";
11. list1.DisplayList();
12.
13. list2.AddNodeAtTail(23);
14. list2.AddNodeAtHead(45);
15. list2.AddNodeAtHead(75);
16. list2.AddNodeAtTail(29);
17. list2.DeleteNode(45);
18. cout<<"\nlist2 after perorming few operations:";
19. list2.DisplayList();
20.}

16. Data Structures & Algorithms
What about
•2-Way linked list (or doubly linked list)
•1-Way circular linked list
•2-Way circular linked list