Data Structures - City University of New York

CSC212 CSC212 Data Data Structure Structure Lecture 8 The Bag and Sequence Classes with Linked Lists Instructor: George Wolberg Department of Computer Science City College of New York @ George Wolberg, 2016 1 Reviews: Reviews: Node Node and and Linked Linked List List Node a class with a pointer to an object of the node class core structure for the linked list two versions of the link functions

why and how? @ George Wolberg, 2016 2 class node { public: // TYPEDEF typedef double value_type; The The Complete Complete node node Class Class Definition Definition // CONSTRUCTOR node( const value_type& init_data = value_type( ), node* init_link = NULL ) { data = init_data; link = init_link; } The node class is fundamental to linked lists The private member variables // Member functions to set the data and link fields:

default argument given by the value_type default constructor void set_data(const value_type& new_data) { data = new_data; } data_field void set_link(node* new_link) { link = new_link; } link_field // Constant member function to retrieve the current data: value_type data( ) const { return data; } The member functions include: // Two slightly different member functions to retrieve // the current link: const node* link( ) const { return link; } node* link( ) { return link;} A constructor Set data and set link private: value_type data; Retrieve data node* link; and retrieve link

Why TWO? p. 213-4 }; @ George Wolberg, 2016 3 Reviews: Reviews: Node Node and and Linked Linked List List Linked Lists Traverse How to access the next node by using link pointer of the current node the special for loop size_t list_length(const node* head_ptr) { const node *cursor; size_t count = 0; for (cursor = head_ptr; cursor != NULL; cursor = cursor->link()) count++; return count; } @ George Wolberg, 2016

4 Reviews: Reviews: Node Node and and Linked Linked List List Insert Insert at the head set the head_ptr and the link of the new node correctly Insert at any location @ George Wolberg, 2016 cursor pointing to the current node need a pre-cursor to point to the node before the current node (two approaches) the third approach: doubly linked list 5

Reviews: Reviews: Node Node and and Linked Linked List List Delete Delete at the head set the head_ptr correctly release the memory of the deleted node Delete at any location @ George Wolberg, 2016 cursor pointing to the current node need a pre-cursor to point to the node before the current node (two approaches) the third approach: doubly linked list 6

Key Key points points you you need need to to know knowToolkit Code Linked List Toolkit uses the node class which has The functions in the Toolkit are not member functions of the node class set and retrieve functions length, insert(2), remove(2), search, locate, copy,... compare their Big-Os with similar functions for an array They can be used in various container classes, such as bag, sequence, etc. @ George Wolberg, 2016 7

Container Container Classes Classes using using Linked Linked Lists Lists Bag Class with a Linked List Sequence Class with a Linked List Specification Class definition Implementation Testing and Debugging Design suggestion difference from bag Arrays or Linked Lists: which approach is better? Dynamic Arrays Linked Lists Doubly Linked Lists

@ George Wolberg, 2016 8 Our Our Third Third Bag Bag -- Specification Specification The documentation nearly identical to our previous bag The programmer uses the bag do not need to know know about linked lists. The difference No worries about capacity therefore no default capacity no reserve function because our new bag with linked list can grow or shrink

easily! @ George Wolberg, 2016 9 Our Our Third Third Bag Bag Class Class Definition Definition The invariant of the 3rd bag class the items in the bag are stored in a linked list (which is dynamically allocated) the head pointer of the list is stored in the member variable head_ptr of the class bag The total number of items in the list is stored in the member variable many_nodes. The Header File (code) @ George Wolberg, 2016 10

Our Our Third Third Bag Bag Class Class Definition Definition How to match bag::value_type with node::value_type class bag { public: typedef node::value_type value type; ...... } Following the rules for dynamic memory usage Allocate and release dynamic memory The law of the Big-Three @ George Wolberg, 2016 11 Our Our Third Third Bag Bag -- Implementation Implementation

The Constructors Overloading the Assignment Operator release and re-allocate dynamic memory self-assignment check The Destructor default constructor copy constructor return all the dynamic memory to the heap Other functions and the code @ George Wolberg, 2016 12 Sequence Sequence Class

Class with with Linked Linked List List Compare three implementations using a fixed size array (assignment 2) using a dynamic array (assignment 3) using a linked list (assignment 4) What are the differences? member variables value semantics Performance (time and space) @ George Wolberg, 2016 13 Sequence Sequence Design Design Suggestions Suggestions

Five private member variables many_nodes: number of nodes in the list head_ptr and tail_ptr : the head and tail pointers of the linked list cursor : pointer to the current item (or NULL) precursor: pointer to the item before the current item why tail_ptr - for attach when no current item for an easy insert (WHY) Dont forget the dynamic allocation/release the value semantics and the Law of the Big-Three @ George Wolberg, 2016 14

Sequence Sequence Value Value Semantics Semantics Goal of assignment and copy constructor Can we just use list_copy in the Toolkit? make one sequence equals to a new copy of another list_copy(source.head_ptr, head_ptr, tail_ptr); Problems ( deep copy new memory allocation) many_nodes OKAY head_ptr and tail_ptr OKAY How to set cursor and precursor ? @ George Wolberg, 2016 15 Dynamic Dynamic Arrays

Arrays vs vs Linked Linked Lists Lists Arrays are better at random access Linked lists are better at insertions/ deletions at a cursor O(1) vs O(n) Doubly linked lists are better for a two-way cursor O (1) vs. O(n) for example for insert O(1) vs. O(n) Resizing can be Inefficient for a Dynamic Array re-allocation, copy, release @ George Wolberg, 2016

16 Reading Reading and and Programming Programming Assignments Assignments Reading after Class Chapter 6 Programming Assignment 4 Detailed guidelines online! @ George Wolberg, 2016 17

Recently Viewed Presentations

  • PowerPoint Presentation

    PowerPoint Presentation

    Shadow Pricing Requirements. The shadow price is the net asset value per share of a qualifying external investment pool, calculated using total investments measured at fair value at the calculation date. A pool should calculate its shadow price at a...
  • CS G140 Graduate Computer Graphics

    CS G140 Graduate Computer Graphics

    Fractal Form of a Romanesco Broccoli photo by Jon Sullivan L-Systems An L-system or Lindenmayer system, after Aristid Lindenmayer (1925-1989), is a formal grammar (a set of rules and symbols) most famously used to model the growth processes of plant...
  • Using these slides - euro-online.org

    Using these slides - euro-online.org

    Using these slides 'Slide-show' allows the animation that shows how the argument on each slide develops. There are notes under each slide, not visible in slide show, which contain useful or important additional information
  • What is Qualitative Research?

    What is Qualitative Research?

    Key Terms: Paradigms. Paradigm: "the basic belief system or worldview that guides the investigator, not only in choices of method but in ontological and epistemologically fundamental ways."(Guba & Lincoln, 1994)
  • Presentation for perspective graduate students ... - UCSB Physics

    Presentation for perspective graduate students ... - UCSB Physics

    Astrophysical upper limit on SUM of neutrino masses ~0.3eV COLD WARM HOT Warm Dark Matter Intermediate case. E.g. sterile neutrinos Generically distribution function can be described by Warm Dark Matter Since WDM decouples when it's relativistic its abundance is given...
  • PowerPoint Presentation

    PowerPoint Presentation

    "Oxford Lasers: a laser micromachining system integrator" NanoKTN, Workshop on Graphene supply chain, Institute of Physics, London, 28 November 2013 TheHellenic Physical Society (Ε.Ε.F.) is a non-profit Scientific Society, founded in 1930, that represents the Greek scientists of Physics, of...
  • Seg 2 Risk Awareness Fact Sheets - michigan.gov

    Seg 2 Risk Awareness Fact Sheets - michigan.gov

    Author: Michigan Department of State Created Date: 11/16/2016 07:41:20 Title: Seg 2 Risk Awareness Fact Sheets Subject: Driver Education Keywords
  • Thermodynamic Control of Reactions - Oneonta

    Thermodynamic Control of Reactions - Oneonta

    The reaction _____ favored by enthalpy. At this temperature, the reaction is controlled by _____. Section 19.3 Free Energy Bill Vining SUNY College at Oneonta Putting S, H and Temperature Together Gibb's Free Energy: G = H - T S...