variable size objects

Dynamic storage and linked list go hand-in-hand. Yes, one can use an array of pointers to organize the dynamic objects. But, linked list is almost always the consequence of dynamic storage (I will use storage and object synonymously). So, where do we use dynamic storage in real life?

Online Shopping Cart

Suppose that we will create shopping application similar to Amazon. When a customer comes into our store, we create a customer object to keep track of his/her behavior. What would that customer object look like?

Customer purchases items by add-to-cart. What would that cart object look like? Cart has a collection of items, right? Collection of items is also referred as container in C++ STL library. Shall we store items as array or linked list? If you're not clear about array design, please visit this array page first.

One important factor to consider is the items object. If the items object has pictures, descriptions, etc, then it is going to be variable size. Given the quantity of items, I don't think we want to have it as a "fixed size" object which needs to have a "maximum size". The variable-size decision here has consequences. It means that the cart object can not be an array of items. However, it can be array of items pointers.

The other design choice is to store collection of all items as a linked list in cart. It is the most flexible approach to accommodate "shoppers without borders" (hmmm, that's a good club name, surely have many members). Not only we can handle variable number of items in a shopping cart, but also allow each item to have variable size.

Still not convinced, one more example:

Message Packets in Network Routers

A network router is like a traffic cop. It directs message packets coming from an incoming connection to an outgoing connection. What would that packet object look like? Since a packet may be huge or tiny in size, a static allocation is not efficient. Furthermore, after deciding where a packet should go, router needs to move the packet from its incoming connection to its outgoing connection. Moving a static packet from one connection to another requires "copying" the packet. Copy can be an expensive proposition when data size is non-trivial.

We will talk more about queue in later part of this class. But, for now, I hope you're convinced that dynamic storage is an essential part of the computer programming.

Complexity

Variable size object is a good reason to use linked list. Do we have reason to use linked list for fixed size objects?

Yes, we do. It is advantageous to use linked list for certain operations. For example, insert an object into an array of n objects takes O(n). Insertion into a linked list of n objects takes O(1). Delete an object has the same effect. If you're not clear, it is time to review big O notation.

Like many things in computer, the proper choice of data structure depends on applications. The essential part of learning is to understand the trade-offs, so that you can make the right choice.