Linked Lists Implementation Method 1.ppt

Linked lists use an entirely different strategy: linked lists allocate memory for each element separately and only when necessary. Disadvantages of Arrays.

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