/ [Comp Sci Dept]
/ [R J Botting]
Mon May 21 07:23:22 PDT 2007
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 ]
- Some problems demand a dynamic data structure because you can't say how much data is needed, until after the program is running.
- It takes more programming to implement a reliable dynamic data structure than any other kind of data structure.
- A dynamic data structure can go wrong because you forget to allocate memory before you use it.
- A dynamic data structure can suffer from a memory leak if storage is allocated but never deleted.
- Use Dynamic Data Structures only when you have to.
- Buy, borrow, copy, reuse, ... dynamic data structures rather than writing them yourself.
Use the Standard Template Library
- Plan to spend a lot of thought and time getting Dynamic structures right.
- Spread time and cost over many uses by using templates.
[ templates.html ]
- Draw lots of pointer diagrams.
- Write lots of useful comments.
- Use conditions to guard every asterisk and arrow from working on a NULL pointer.
- Once its working, reuse it, and never, ever change it.
- Collect a personal portfolio of dynamic data structure templates.
Take a Data Structures class: CS330
. . . . . . . . . ( end of section Rough Notes on Dynamic Data Structures) <<Contents | End>>
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.
Dynamic_Data_Structure::=A collection of data than can grow by allocating new memory and shrink by reallocating memory as the program runs.
Link::=Connects two nodes in a Dynamic_Data_Structure. Each is a pointer from one node to the other..
Node::=A piece or item of information in a Dynamic_Data_Structure that is deleted or created as a whole as needed.
pointer::=A variable that is either NULL or contains the address of another piece of data.
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".
stack::=A collection of data , kept in order, that can have new items pushed on to it and popped of in the reverse order.
queue::=A collection of items, kept in order, that can only have items enter at one end and leave at the other.
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.
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..
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..
vector::=data of the same type indexed by a range of integer values. It is not easy to insert and delete data.
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.
constructor::=a member function with the same name as the class that is called automatically when a variable is decalred of that class.
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.
traverse::=To visit each item or node in a list in turn.
iterator::=an object that can be used to traverse a data structures.
TBA::="To Be Announced", something I have to do.
TBD::="To Be Done", something you have to do.
Dia::="A free Open Source Diagramming tool for Linux, Windoze, etc. ".
YAGNI::="You Ain't Gonna Need It".
DRY::="Don't Repeat Yourself".