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

• 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.

My Rules

• 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.

  ---

  1. Spread time and cost over many uses by using templates. [ templates.html ]
  2. Draw lots of pointer diagrams.
  3. Write lots of useful comments.
  4. 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>>

Glossary