Skip to main contentCal State San Bernardino / [CNS] / [Comp Sci Dept] / [R J Botting] >> [CSci202] >> linked
[Index] [Schedule] [Syllabi] [Text] [Labs] [Projects] [Resources] [Search] [Contact] [Grading]
Notes: [01] [02] [03] [04] [05] [06] [07] [08] [09] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20]
Mon May 21 07:23:22 PDT 2007

Contents


    Notes on Dynamic Data Structures

      A Problem that needs a complex linked structure

      Construct a family tree showing all the people, their marriages, their children, their brothers and sisters, etc.

      How Linked Data Works

      Here is a story showing how linked list works: Each part of the list knows where to find just the next part. True story:
        I wanted to find wife's sister's father_in_law's address to thank him for giving me a lift last time I flew to the UK.

       		I -> wife->sister->husband->father->Address.

        I ask my wife for her sister's phone number. I phone my wife's sister. She doesn't remember the address. She does remember her husband's phone number. She phones her husband. He knows his father's address. He Emails it to me. Now I know the address I needed.

      In the above the phone numbers and addresses are like the contents of pointers in a linked list.

      How Dynamic Data is Implemented

      The trick to implement solutions to the above problem is to store the addresses of data and objects. Stored addresses are called pointers: [ pointers.html ]

      Examples of links and linked lists

      [ dl.cpp ] [ ll.cpp ] [ sl.cpp ]

      Key Facts

      My Rules

    . . . . . . . . . ( end of section Rough Notes on Dynamic Data Structures) <<Contents | End>>

    Glossary

  1. Data_Structure::=A collection of data in random access memory that follows a special set of rules. Can also be thought of as a small temporary data-base.

  2. Dynamic_Data_Structure::=A collection of data than can grow by allocating new memory and shrink by reallocating memory as the program runs.

  3. Link::=Connects two nodes in a Dynamic_Data_Structure. Each is a pointer from one node to the other..

  4. Node::=A piece or item of information in a Dynamic_Data_Structure that is deleted or created as a whole as needed.

  5. pointer::=A variable that is either NULL or contains the address of another piece of data.

  6. NULL::=A special value that takes the same amount of storage as an address and yet is not a possible address. In C and C++ NULL is converted to false in tests. It is used to indicate the end of a dynamic list. Proverb: Do not follow the NULL pointer for surely madness will meet you there".

  7. stack::=A collection of data , kept in order, that can have new items pushed on to it and popped of in the reverse order.

  8. queue::=A collection of items, kept in order, that can only have items enter at one end and leave at the other.
  9. deque::=Double ended queue. Can add and delete items at either end. Access to items at either end. No access to items that are not at the ends.
  10. set::=A collection of non-repeating items. An item is either in the set or not in the set. Items can be added to the set and removed from it..

  11. bag::=A collection of unordered items. An item is in the bag zero or more times. Items can be added to the bag and removed from it..

  12. vector::=data of the same type indexed by a range of integer values. It is not easy to insert and delete data.

  13. list::=`An ordered set of items that can be searched, have new data inserted and old data deleted anywhere in it, but is not normally indexed.

  14. constructor::=a member function with the same name as the class that is called automatically when a variable is decalred of that class.

  15. destructor::=a member function whose name starts with a tilde and ends with the name of the class that is called automatically when the object goes out of scope.

  16. traverse::=To visit each item or node in a list in turn.

  17. iterator::=an object that can be used to traverse a data structures.

    Abbreviations

  18. TBA::="To Be Announced", something I have to do.
  19. TBD::="To Be Done", something you have to do.
  20. Dia::="A free Open Source Diagramming tool for Linux, Windoze, etc. ".
  21. YAGNI::="You Ain't Gonna Need It".
  22. DRY::="Don't Repeat Yourself".

End