Linked List Implementation in Programming Fundamentals

ECE 244 Programming Fundamentals Lec. 16: Linked list Ding Yuan ECE Dept., University of Toronto http://www.eecg.toronto.edu/~yuan

Background Much of designing programs has to do w/ figuring out the best way to organize data Many standard data structures have been devised and studied Some are used over and over again: Arrays Linked lists Ordered, FIFO, FILO (stack), doubly linked list Trees Hash tables Learn how to use them; which are best for what

Contents of this lecture Linked list 3 5 23 187 Recall: A collection of nodes that are linked to one another via pointers; used to store data in some order; last node point to NULL This lecture will implement a complete, sorted linked list

Node class Node { private: int data; Node *next; public: Node() { data = 0; next = NULL; } Node(int d) { data = d; next = NULL; } Node(int d, Node *n) { data = d; next = n; } int getData() const { return data; } void setData (int _d) { data = _d; } Node *getNext() const { return next; } void setNext(Node *_n) { next = _n; } }

Defining the List The List class needs to Keep the list sorted Keep track of head of the list Support basic operations Inserting (keep list sorted) Deleting Searching Copying one list from another list Have a destructor that properly deletes the list

Declaration of class List class List { private: Node *head; public: List(); ~List(); void insertValue (int); bool valueExists (int); bool deleteValue (int); List (const List & original); List & operator= (const List & original); .. .. };

Searching the list (solution #1) bool List::valueExists(int _data) { for (Node *cur = head; cur != NULL; cur = cur->getNext()) { if (cur->getData() == _data) { return true; } } return false; } Will it work if List is empty? Will it work if value V is not in List? You cannot use cur->next When developing code like this, always ask:

Solution #2: optimization If _data is not in the list, we don t need to always search through the entire list! bool List::valueExists(int _data) { for (Node *cur = head; cur != NULL; cur = cur->getNext()) { if (cur->getData() == _data) { return true; } if (cur->getData() > _data) { return false; } } return false; }

Comparing ordered vs. unordered list if _data is not in the list, and list is unordered, how much of the list do we have to search through? Entire list! if _data is not in the list, and the list is ordered, how much do we have to search through? Best case: one node deep! Worst case: All of it! Average: Half of the list

Insert into List Need to find the right location Special cases to consider: Inserting at the head of the list: need to change head Inserting at the end: make sure the new node points to NULL Inserting in middle: make sure next pointers are properly updated

Idea Need a pointer, p, to advance through the list Stop at the a node when p->getData() > _data, or p==NULL But when it stops, it s too late! We lost track of the previous node Solution: use another pointer, prev, to follow p If we have a doubly linked list, this is no longer a problem 3 5 23 187

Implementation void List::insertValue (int _data) { Node *n = new Node(_data); Node *p = head; Node *prev = NULL; while (p != NULL && p->getData() < _data) { prev = p; p = p->getNext(); } n->setNext(p); if (prev == NULL) // head of the list! head = n; else prev->setNext(n); }

Deleting Similar to insert, use two pointers But look for node whose value == _data Return true if a _data is found (and deleted); return false if _data is not found in the list X 3 5 23 187

1 bool List::deleteValue(int _data) { 2 Node *p = head, *prev = NULL; 3 while (p != NULL && p->getData() != _data) { 4 prev = p; 5 p = p->getNext(); 6 } 7 if (p == NULL) // _data is not in the list 8 return false; 9 /* Remove the node pointed by p from the list. */ 10 if (prev == NULL) // p is the head of the list! 11 head = p->getNext(); 12 else 13 prev->setNext(p->getNext()); 14 delete p; 15 return true; 16 } Check: does it work - if list is empty - if _data not in list - if _data first node - if _data last node - if _data in the middle 3 5 23 187

Destructor You new, you delete List::~List() { Node *p; while (head != NULL) { p = head; head = p->getNext(); delete p; } }

Copy constructor Recall: C++ does shallow copy by default We need to create constructor that does deep copy p 3 5 23 187 n np 3 5 23 187

1 List::List (const List & original) { 2 Node *p = original.head; 3 Node *np = NULL; 4 head = NULL; 5 while (p != NULL) { 6 Node *n = new Node (p->getData()); 7 if (np == NULL) head = n; 8 else np->setNext(n); 9 p = p->getNext(); 10 np = n; 11 } 12 } p 3 5 23 187 np n 3 5 23 187

operator=: lhs = rhs Very similar to copy constructor, BUT we have to deal with copy(lhs) is not empty original(rhs) is the same list as copy(lhs) I.e., lilst1 = 1istl List & List::operator=(const List & original) { if (&original == this) return (*this); if (head != NULL) { // empty the list as in destructor .. .. } // copy list as copy constructor return (*this); }

Linked list in real world Dynamic memory management Free blocks are modeled as linked list Successor links B A 4 4 4 4 6 6 4 4 4 4 C Predecessor links Recent files E.g., in PowerPoint, YouTube (video history), Adobe Acrobat, MS word, etc.