CMP2006_Lecture4_LinkedLists.pptx

DATA STRUCTURES The Linked List Abstract Data Type Updated 2014 – David White, 2019 – Philip Smith EXPECTED OUTCOMES At the end of this lecture, the student should be able to:  Explain the various operations of linear linked lists  Specify pseudo-code definitions fo...

DATA STRUCTURES The Linked List Abstract Data Type Updated 2014 – David White, 2019 – Philip Smith EXPECTED OUTCOMES At the end of this lecture, the student should be able to:  Explain the various operations of linear linked lists  Specify pseudo-code definitions for the various operations of linear linked-lists  Discuss linear linked-list structures such as singly, doubly and circularly linked-lists TOPICS  The Linked List  Pictorial Representation of a Linked List  Linked List Operations  Singly linked lists  Doubly linked lists  Circularly linked lists THE LINKED LIST  A linked list is a linear list data structure which consists of a list of nodes or elements in a logical but not necessarily physical sequence  A linked list is a dynamic data structure, which means memory is allocated for each node at run time  Each node in the list contains a data potion and a link portion  The list is made up of multiple nodes. The list keeps track of a special node called the Head that references of the start of the list at all times  Each node contains a pointer to its successor node in the list, except the last node, which uses a special marker to indicate that no node follows it.  Each successor node follows its predecessor node logically but not necessarily physically, so makes better use of available space. Therefor memory allocation for the entire linked list does not have to be contiguous.  Still have to possibly traverse the entire list to search for a particular value because it’s a general list  THE LINKED LIST A Typical Node 17 Algorithm for a Linked Lists Node NODE Data Data Link Portion NextNode Portion END NODE Head points to the start of the list Head 17 Empty node pointer  PICTORIAL REPRESENTATION OF LINKED LIST Logical Representation Head 10 17 18 23 null Sample layout in Head memory null FA74 FA8 FA9 FA8 10 18 17 23 C 4 4 FA74 FA7C FA84 FA8C FA94 FA9C LINKED LIST OPERATIONS  Create the linked list  Destroy the linked list  Insert at the front  Insert in the middle  Insert at the back  Display all nodes in list  Search for a node  Delete a node  Count the number of nodes  Check if the list is full  Check if the list is empty CREATE THE LINKED LIST Algorithm CreateList() Create an empty linked list Pre: Nothing Post: An empty linked list is created Return: The location of the head of the list Declare Head as NODE Head ← empty node pointer Return Head End CreateList INSERT AT FRONT Algorithm InsertAtFront(ref Head , val DataToAdd ) Insert a new node at the front of a linked list Pre: Head points to the start of the linked list, DataToAdd is the data to be inserted Post: Data is placed in a new node and inserted at the front of the list Return: nothing Declare Temp as NODE Allocate memory for Temp If memory was allocated successfully then Temp->Data ← DataToAdd Temp->NextNode ← empty node pointer If Head = empty node pointer Head ← Temp Else Temp->NextNode ← Head Head ← Temp End if Else `Write “Out of memory, unable to insert node” End if End InsertAtFront INSERT AT THE BACK Algorithm InsertAtBack(ref Head , val Data ) Insert a new node at the back of a linked list Pre: Head points to the start of the linked list, Data is the data to be inserted Post: Data is placed in a new node and inserted at the back of the list Return: nothing Declare Temp1, Temp2 as NODE Allocate memory for Temp1 If memory was allocated successfully then Temp1->Data ← Data Temp1->NextNode ← empty node pointer If Head = empty node pointer Head ← Temp1 Else Temp2 ← Head While (Temp2->NextNode empty node pointer) Temp2 ← Temp2->NextNode End While Temp2->NextNode ← Temp1 End if Else Write “Out of memory, unable to insert node” End if End InsertAtBack SEARCH FOR A NODE Algorithm SearchForNode(ref Head , val Key ) Search a linked list for a node containing Key in its data section Pre: Head points to the start of the linked list, Key is the value to search for Post: The linked list is searched to see if the Key is found Return: true if the Key was found, else false if it was not found Declare Temp as NODE Temp ← Head While (Temp empty node pointer) If Temp->Data = Key Return true End if Temp ← Temp->NextNode End While Return false End SearchForNode COUNT THE NUMBER OF NODES Algorithm CountNodes(ref Head ) Counts the number of nodes in a linked list Pre: Head points to the start of the linked list Post: The number of nodes in the linked list is counted Return: The number of nodes in the linked list Declare Temp as NODE Declare Count as integer Temp ← Head Count ← 0 While (Temp empty node pointer) Increment Count Temp ← Temp->NextNode End While Return Count End CountNodes DESTROY THE LINKED LIST (DELETE ALL NODES) Algorithm DestroyList(ref Head ) Destroy an existing linked list Pre: Head points to the start of the linked list Post: The linked list is destroyed by removing all its nodes Return: nothing Declare Temp as NODE While (Head empty node pointer) Temp ← Head Head ← Head->NextNode Deallocate Temp End While End DestroyList CHECK IF THE LIST IS FULL Algorithm CheckIfListFull() Checks a linked list to determine if it can hold any more nodes Pre: Nothing Post: Memory is checked to see if a temporary node could be allocated Return: true if the temporary node was successfully allocated, else false if not Declare Temp as NODE Allocate memory for Temp If memory was allocated successfully then Deallocate Temp Return false Else Return true End if End CheckIfListFull CHECK IF THE LIST IS EMPTY Algorithm CheckIfListEmpty(ref Head ) Checks a linked list to determine if it is empty Pre: Head points to the start of the linked list Post: The list is checked to determine if it is empty Return: true if Head points to the empty node pointer, else false if not If Head = empty node pointer Return true Else Return false End if End CheckIfListEmpty  C++ Code Java Code //Node.h THE NODE CLASS //Node.java #include using namespace std;Remember to enclose the class in the public class Node class Node preprocessor directives: { { #ifndef CLASSNAME private int Data; private: #define CLASSNAME private Node NextNode; int Data; #endif public Node() Node * NextNode; public: Data { Node() Portion Link Data = 0; { NextNode = null; Portion } Data = 0; NextNode = NULL; public void SetData(int d) } Construct { Data = d; void SetData(int d) or } { public void SetNextNode(Node Data = d; nn) } { void SetNextNode(Node *nn) NextNode = nn; { } NextNode = nn; public int GetData() } { int GetData() Accessors & return Data; { Mutators } return Data; public Node GetNextNode() } { Node * GetNextNode() return NextNode; { } return NextNode; } } };  C++ Code Java Code //LinkedList.h THE LINKED LIST //LinkedList.java #include “Node.h” class LinkedList CLASS Remember to enclose the class in the preprocessor directives: public class LinkedList { { #ifndef CLASSNAME private Node Head; private: #define CLASSNAME public LinkedList() Node * Head; public: { #endif LinkedList() Head = null; { Head } Head = NULL; Pointer public void InsertAtFront(int d) } { void InsertAtFront(int d) Constructo Node temp = new Node(); { if(temp != null) Node * temp = new Node(); r { If(temp != NULL) temp.SetData(d); { temp.SetNextNode(null); temp->SetData(d); if(Head == null) temp->SetNextNode(NULL); if(Head == NULL) { { Head = temp; Head = temp; } } else else { { Insert At Front temp.SetNextNode(Head); temp->SetNextNode(Head); Operation Head = temp; Head = temp; } } } } else else { { System.out.println(“Memory coutInsertAtFront(18); Invoke the Insert At List.InsertAtFront(23); List->InsertAtFront(17); Front Operation List.InsertAtFront(18); List->InsertAtFront(10); List.InsertAtFront(17); List.InsertAtFront(10); system(“pause”); } return 0; } } }; SYNTAX DIFFERENCES BETWEEN C+ + AND JAVA There are 6 key syntax differences between the two languages (based on covered content:  Access specifiers: Java requires specifiers inline for classes, attributes and methods while C++ uses the “:” to group specifiers  Use of pointers in C++; Java doesn’t use pointers  When using pointers in c++ we use the “->” while in java we use the “.”  Output and input keywords in both languages  Library references  C++ uses NULL while Java uses null. SINGLY LINKED LIST  The linear linked list we have studied so far is formally known as a singly linked list  This is so termed because each node has a single link to the next node  There are other types and variations of linear linked list, including:  Doubly linked list  Circular linked list  Research what other types of linked list you can find DOUBLY LINKED LIST  A doubly linked list is a linked list in which each node has a pointer both to its successor and its predecessor  The first nodes previous node pointer does not point to a predecessor and the last nodes next node pointer does not point to a successor  The Head keeps track of the start of the list and the Tail keeps track of the end of the list  A doubly linked list can be traversed from front to back or from back to front starting from the Head or the Tail respectively  THE DOUBLY LINKED LIST A Typical Node 17 Algorithm for a Linked Lists Node NODE Next node Data Data Previous node pointer PrevNode Portion pointer NextNode END NODE Head Tail 17 Empty node pointer Empty node pointer  DOUBLY LINKED LIST Hea Tail d null 10 17 18 23 null null Head Tail FA8 FA8 FA9 FA7 FA8 FA8 10 18 17 23 C C 4 4 4 4 FA74 FA7C FA84 FA8C FA94 FA9C null CIRCULAR LINKED LIST  A circular linked list is a linked list in which each node has a pointer to its successor.  The last node in this list has its next node pointer pointing to the first node in the list (the head)  The Head keeps track of the start of the list and the Tail keeps track of the end of the list  CIRCULAR LINKED LIST 17 Hea d 10 18 23 Tail EFFICIENCY OF A LINKED LIST  Compare the efficiency of these linked list operations with that of the array operations you discussed in previous classes  Traversing an array and a linked list have the same efficiency  An array is more efficient that a linked list in terms of direct storage and retrieval THINGS TO DO  The algorithms for the Display all Nodes in the List, Insert in the Middle and Delete a Node operations were not given in this lecture  Can you write them yourself?  What is the efficiency of these operations?  In your tutorial and lab classes this week, write your own version of the linked list ADT including both the data and the operations  Implement the full singly linked list ADT with all its operations using either C++ or Java  Implement the full doubly and circular lists in your free time