Question? Leave a message!

Linked Lists

Linked Lists
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
ECE 250 Algorithms and Data Structures Linked Lists Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.Linked Lists 2 Outline In this topic, we will look at linked lists – The Node and List classes – Accessors and mutators – The implementation of various member functions – Stepping through a linked list – Defining the copy and assignment operator – Defining move constructors and move assignment operators – Discussed efficienciesLinked Lists 3 Definition A linked list is a data structure where each object is stored in a node As well as storing data, the node must also contains a reference/pointer to the node containing the next item of dataLinked Lists 4 Linked Lists 1 We must dynamically create the nodes in a linked list Thus, because new returns a pointer, the logical manner in which to track a linked lists is through a pointer A Node class must store the data and a reference to the next node (also a pointer) Linked Lists 5 Node Class 1 The node must store data and a pointer: class Node private: int element; Node next_node; public: Node( int = 0, Node = nullptr ); int retrieve() const; Node next() const; ;Linked Lists 6 Node Constructor 1.1 The constructor assigns the two member variables based on the arguments Node::Node( int e, Node n ): element( e ), next_node( n ) // empty constructor The default values are given in the class definition: class Node private: int element; Node next_node; public: Node( int = 0, Node = nullptr ); int retrieve() const; Node next() const; ;Linked Lists 7 Accessors The two member functions are accessors which simply return the element and the next_node member variables, respectively int Node::retrieve() const return element; Node Node::next() const return next_node; Member functions that do not change the object acted upon are variously called accessors, readonly functions, inspectors, and, when it involves simply returning a member variable, gettersLinked Lists 8 Accessors In C++, a member function cannot have the same name as a member variable Possible solutions: Member Member Variables Functions Vary capitalization next_node Next_node() or NextNode() Prefix with “get” next_node get_next_node() / getNextNode() Use an underscore next_node_ next_node() Different names next_node next() Always use the naming convention and coding styles used by your employer—even if you disagree with them • Consistency aids in maintenanceLinked Lists 9 Linked List Class Because each node in a linked lists refers to the next, the linked list class need only link to the first node in the list The linked list class requires member variable: a pointer to a node class List private: Node list_head; // ... ;Linked Lists 10 Structure To begin, let us look at the internal representation of a linked list Suppose we want a linked list to store the values 42 95 70 81 in this orderLinked Lists 11 Structure A linked list uses linked allocation, and therefore each node may appear anywhere in memory Also the memory required for each node equals the memory required by the member variables – 4 bytes for the linked list (a pointer) – 8 bytes for each node (an int and a pointer) • We are assuming a 32-bit machineLinked Lists 12 Structure Such a list could occupy memory as follows: Linked List ObjectLinked Lists 13 Structure The next_node pointers store the addresses of the next node in the listLinked Lists 14 Structure Because the addresses are arbitrary, we can remove that information:Linked Lists 15 Structure We will clean up the representation as follows: list_ We do not specify the addresses because they are arbitrary and: – The contents of the circle is the element – The next_node pointer is represented by an arrowLinked Lists 16 Operations First, we want to create a linked list We also want to be able to: – insert into, – access, and – erase from the elements stored in the linked listLinked Lists 17 Operations We can do them with the following operations: – Adding, retrieving, or removing the value at the front of the linked list void push_front( int ); int front() const; void pop_front(); – We may also want to access the head of the linked list Node head() const; Member functions that may change the object acted upon are variously called mutators, modifiers, and, when it involves changing a single member variable, settersLinked Lists 18 Operations All these operations relate to the first node of the linked list We may want to perform operations on an arbitrary node of the linked list, for example: – Find the number of instances of an integer in the list: int count( int ) const; – Remove all instances of an integer from the list: int erase( int );Linked Lists 19 Linked Lists Additionally, we may wish to check the state: – Is the linked list empty? bool empty() const; – How many objects are in the list? int size() const; The list is empty when the list_head pointer is set to nullptrLinked Lists 20 Linked Lists Consider this simple (but incomplete) linked list class: class List private: Node list_head; public: List(); // Accessors bool empty() const; int size() const; int front() const; Node head() const; int count( int ) const; // Mutators void push_front( int ); int pop_front(); int erase( int ); ;