Chapter 10: Elementary Data Structures: Arrays, Linked Lists, and Trees

Welcome to Last Minute Lecture.

This free chapter overview is designed to help students review and understand key concepts.

These summaries supplement not replaced the original textbook and may not be redistributed or resold.

For complete coverage, always consult the official text.

Welcome back to the Deep Dive.

You know, when we use computers, we don't often think about the magic that happens behind the scenes to make everything work.

Oh, absolutely.

But there are some really fundamental structures that are kind of the unsung heroes of how computers organize and manage information.

We're talking about those basic building blocks called elementary pointer based data structures.

Yeah, think of them as the foundations upon which all the software you use is built, from the apps on your phone to the massive databases that power the internet.

So in this deep dive, we're going to get down to the nuts and bolts of these structures,

arrays,

matrices, stacks, queues, linked lists, and rooted trees.

And our goal is to really understand how they're constructed at a basic level, like what makes each one unique, and also the trade -offs involved in choosing one over another for a specific task.

And to kick things off, let's start with, well, the most basic of the basic, arrays and matrices.

Okay, when we talk about an array, what's that core idea?

So an array is all about storing elements sequentially in memory.

It's like having a row of neatly organized boxes, each box holding one piece of data.

So each box has an address, right?

Exactly.

And that's what allows the computer to find any element super quickly.

It knows the starting address of the array and the size of each box, so it can just do a quick calculation to jump right to the box it needs.

That's what we mean by contiguous memory allocation, everything neatly lined up.

So it doesn't matter if you want the first element or the thousandth, the access time is constant.

Precisely.

No matter where the element is in the array, the computer can access it in the same amount of time.

But I remember from my coding days that usually everything in an array has to be the same size.

Why is that?

Well, if the elements had varying sizes, the computer wouldn't know how many bytes to skip over to get to the next one.

That nice neat organization would fall apart, and finding elements would become much But hold on, what if you need to store different kinds of data in an array, things that aren't the same size?

Ah, there's a clever trick for that.

Instead of storing the actual data in the array, we can store pointers.

Pointers, right?

Those memory addresses.

Exactly.

Pointers themselves have a fixed size, so the array stays nice and organized.

Each pointer can then point to a piece of data anywhere in memory, regardless of its size.

So we get to keep the speed of direct access while still being able to store data of varying sizes.

Clever.

Now let's move on to matrices, those two -dimensional grids that are like arrays, but, well, squared.

Yeah, think of a spreadsheet or a table with rows and columns.

It's a natural way to represent many kinds of data.

But how do we store this two -dimensional structure in the computer's memory, which is essentially a one -dimensional line?

That's where things get a little more interesting.

There are two main methods, row major order and column major order.

In row major order, you store all the elements of the first row, then all the elements of the second row, and so on, just like reading a book.

So you're basically unrolling the grid row by row.

Exactly.

And in column major order, you do the opposite.

Unrolling the grid column by column, you store all the elements of the first column, then the second, and so on.

Okay, I can picture that.

But why does the order matter?

It can significantly impact performance, especially when you're working with large matrices.

For example, if you're processing a matrix row by row, accessing elements in row major order is generally faster because those elements are stored next to each other in memory.

This can take advantage of how computers cache data, making things run more smoothly.

Makes sense.

Keep related data close together for efficiency.

Now, is storing the entire matrix in one big chunk of memory the only way to do it?

Not necessarily.

There are other approaches that offer more flexibility.

You could, for instance, use an array of arrays, where each element of the main array is a pointer to another array representing a row or a column.

So it's like having a master list, and each entry in the list points to a separate smaller list.

Precisely.

And this allows you to create what are called ragged arrays, where each row or column can have a different number of elements.

So you're not limited to that perfectly rectangular grid structure.

And the source material mentions another technique called block representation.

Yes.

In block representation, we divide the matrix into smaller blocks, and each block is stored contiguously in memory.

This can be particularly beneficial for large matrix operations, making better use of the different levels of memory in a computer.

So again, it's all about optimizing how data is stored to improve performance.

All right, let's shift gears now and talk about two really important dynamic data structures.

Stacks and queues.

Dynamic meaning they can grow and shrink as you add and remove elements.

Exactly.

And the cool thing is they enforce specific rules about how elements are managed.

Let's start with stacks.

What's the fundamental principle there?

Imagine a stack of plates.

You can only add a plate to the top, and you can only remove a plate from the top.

This is what we call last in, first out, or LifeFO.

So the last plate you put on the stack is the first one you take off, like a pile of dirty dishes, sadly.

Yeah.

A perfect analogy.

And we have specific terms for the operations on a stack.

PUSH to add an element to the top, and POP to remove the top element.

Implementing a stack can be quite straightforward using an array.

You just need a way to keep track of where the top of the stack is.

And what happens if you try to pop a plate off an empty stack or add a plate to a stack that's already full?

Those are situations we need to handle carefully in our code to prevent errors.

Trying to pop from an empty stack is called stack underflow, and trying to push onto a full stack is called stack overflow.

Okay, got it.

And the source material emphasizes that basic stack operations, like PUSH, POP, and checking if the stack is empty,

are really fast.

Yes, they take constant time, often denoted as 01, which means the time it takes to perform these operations doesn't depend on how many elements are already in the stack.

That's great for efficiency.

Now let's talk about queues.

How are they different from stacks?

Queues follow a different principle.

First in, first out, or FIFO.

So it's like a line at the grocery store.

The first person in line gets served first.

Exactly.

And just like with stacks, we have specific operations for queues.

IN queue to add an element to the back of the queue, and DE queue to remove an element from the front.

We can also implement a queue using an array, but we need to keep track of both the head and the tail of the queue.

But what happens when we reach the end of the array and want to enqueue more elements, but there's empty space at the beginning?

Ah, that's where the concept of wraparound comes in.

When the tail of the queue reaches the end of the array, if there's space at the beginning, we can simply wrap the tail around to the start of the array, making efficient use of the available space.

So it's like a circular buffer.

Exactly.

And just like with stacks, we need to handle underflow and overflow conditions where we try to dequeue from an empty queue or enqueue into a full one.

And just like stack operations, basic queue operations also take constant time, O1.

So both stacks and queues are efficient for managing dynamic sets of items, but they differ in the order in which elements are processed.

And those differences make them suitable for different kinds of tasks.

Stacks are often used for managing function calls and programming, while queues are great for tasks like scheduling processes in an operating system or managing print jobs.

Okay, I think we're ready to move on to a data structure that offers even more flexibility when it comes to managing data.

Linked lists.

Right, linked lists.

They move away from that contiguous block of memory we see with arrays, right?

Precisely.

In linked lists, the order of elements is determined by pointers rather than their physical location in memory.

Each element, called a node, contains the data itself, often called the key, and a pointer to the next node in the sequence.

So it's like a chain where each link points to the next one.

A perfect analogy.

And we're going to focus on doubly linked lists where each node has two pointers, one to the next node and one to the previous node.

This allows us to traverse the list in both directions.

So you can go forward and backward through the list.

That's handy.

And how do we know where the list begins and ends?

The list has a head pointer that points to the first node.

The last node in the list has its next pointer set to nil, or null, indicating the end.

Similarly, the first node has its previous pointer set to nil.

And if the head pointer itself is nil, it means the list is empty.

Got it.

Now, are there different kinds of linked lists?

Absolutely.

There are singly linked lists which only have the next pointer so you can only traverse them in one direction.

And then there are sorted linked lists where elements are kept in a specific order based on their key.

We also have circular linked lists where the last node's next pointer points back to the first node, creating a loop.

But for this discussion, we'll stick with the unsorted doubly linked list to keep things clear.

Make sense.

So how do we perform basic operations like searching, inserting, and deleting in a doubly linked list?

Let's start with searching.

To find a specific element, we typically start at the head of the list and follow the next pointers until we either find the element we're looking for or reach the end of the list.

So in the worst case, we might have to look at every element in the list.

Exactly.

The worst case time complexity for searching is linear, denoted as n, where n is the number of elements in the list.

But how about inserting an element?

That's where linked lists can really shine.

Because we don't have to shift elements around like in an array.

Precisely.

Adding an element at the beginning of a doubly linked list, let's call it list prepend, is incredibly efficient.

We just need to adjust a few pointers.

The new element's next pointer points to the current head, the current head's previous pointer points to the new element, and then we update the list's head pointer to point to the new element.

This all happens in constant time, O1.

So no matter how long the list is, adding to the beginning always takes the same amount of time.

That's impressive.

What about inserting somewhere in the middle of the list?

If we already have a pointer to the element after which we want to insert, then insertion, which we can call list insert, is also a constant time operation, O1.

We simply adjust the next and previous pointers of the surrounding elements and the new element to link everything up correctly.

And what about deleting an element?

Deleting an element is similar.

If we have a pointer to the element we want to remove, we just need to update the pointers of the elements before and after it to bypass the element being deleted.

This is called list delete, and it also takes constant time, O1.

But what if we don't have a pointer to the element we want to delete?

Then we first need to search for the element, which brings us back to that linear time complexity for the worst case.

So we see a trade -off here.

Linked lists excel at insertions and deletions when we already know where we want to perform them, but accessing an element at a particular position requires traversing the list, which can be slower than direct access in an array.

So choosing between an array and a linked list depends on the specific operations we'll be performing most frequently.

Exactly.

Each data structure has its strengths and weaknesses, and the best choice depends on the task at hand.

Okay, the sorts material mentions something called sentinels when talking about linked lists.

What are those?

Yeah, I was curious about that too.

Sentinels are dummy nodes that we add to the beginning and or end of a linked list.

Think of them as guardians.

Guardians.

Yeah, they simplify our code by eliminating the need to handle special cases for empty lists, or when operating at the very beginning or end of the list.

So they reduce the complexity of handling edge cases.

Precisely.

A common example is a circular doubly linked list with a single sentinel, often called L .nil.

This sentinel sits between the head and the tail, and its pointers wrap around to create a continuous loop.

So even an empty list has this sentinel in place.

Yes, which makes operations like insertion and dilution more consistent, because we're always working with regular nodes and their pointers without having to worry about special cases for an empty list.

And the source material mentions that using a sentinel can also make the search operation slightly more efficient.

You can store the key you're searching for in the central node itself before starting the search.

This guarantees the search loop will always terminate when the key is found, either in a regular element or in the sentinel, potentially saving a few comparisons.

So sentinels streamline things.

Are there any downsides to using them?

They do consume a small amount of extra memory.

If you have a large number of very small lists, this overhead might be a minor concern.

Also, while sentinels can simplify code and potentially lead to small constant factor speed ups, they don't change the overall time of operations in a fundamental way.

So it's a trade -off between code simplicity and a little bit of memory overhead.

All right, we've talked about linear structures.

Shall we move on to how we can represent hierarchical data using linked structures, specifically rooted trees?

Absolutely.

Rooted trees are fundamental in computer science for representing hierarchical relationships like file systems or organizational charts.

So how do we use pointers to represent those relationships?

The basic idea is that each node in the tree is an object containing its data or key and pointers to other nodes in the tree, typically its children.

Okay, let's start with binary trees, the kind where each node can have at most two children.

How are they typically represented?

In a standard binary tree representation, each node x has three pointers.

P pointing to its parent, left pointing to its left child, and right pointing to its right child.

And the root node has no parent, so its p pointer is null.

Exactly.

And if a node doesn't have a left or right child, the corresponding pointer is set to null.

The root of the entire tree t is often accessed through a pointer called t .root.

If t root is null, it means the tree is empty.

Got it.

But what about trees where nodes can have more than two children?

How do we handle that?

That's where the left child, right sibling representation comes in.

Instead of having separate pointers for each child, which could be wasteful if nodes have varying numbers of children, we use just two pointers, left child and right sibling.

Okay, how does that work?

Each node x still has a parent pointer, p.

The left child pointer points to the leftmost child of the node and the right sibling pointer points to the sibling immediately to its right at the same level in the tree.

So the children of a node are essentially linked together in a single list using the right sibling pointers.

Clever.

It's an elegant and efficient solution.

If a node has no children, its left child pointer is null.

If a child is the rightmost sibling, its right sibling pointer is null.

This way we can represent trees with varying numbers of children per node without wasting memory on unnecessary pointers.

And the source material mentions that this representation uses only o n space, where n is the number of nodes in the tree.

That's great for efficiency.

Are there other ways to represent trees?

Yes, there are other specialized representations, like array -based representations for heaps, which are a specific type of binary tree.

Or if you only need to traverse the tree upwards from nodes to the root, you might only need to store parent pointers in each node.

The best representation really depends on the specific requirements of the application.

So just like with the other data structures we've talked about, there's no one -size -fits -all solution.

Precisely.

Choosing the right data structure is all about understanding the trade -offs and making informed decisions based on the problem you're trying to solve.

Well, I think we've covered a lot of ground today.

We've explored how arrays use contiguous memory for fast access, the different ways matrices can be stored in memory, the contrasting principles of stacks and queues, the flexibility of linked lists and the role of sentinels, and the various pointer -based representations for rooted trees.

We've really delved into the core organization of each structure, their implementations using pointers, and their fundamental properties, including memory considerations and the efficiency of their basic operations.

So for our listeners, understanding these foundational building blocks is crucial for appreciating how computers work at a deeper level.

It's about seeing beyond the screen and recognizing the elegance and efficiency of these structures that power the digital world around us.

And it's fascinating to think how these seemingly simple structures are the basis for more complex and powerful data organization techniques that enable everything from the apps on our phones to the vastness of the internet.

Absolutely.

So the next time you're using a piece of software or interacting with a digital system, take a moment to consider how these fundamental structures might be working behind the scenes, quietly organizing and managing information.

And that's it for our deep dive into elementary pointer -based data structures.

We've covered arrays, matrices, stacks, queues, linked lists, and rooted trees,

exploring their basic organization, pointer -based implementations, and key properties.

Thanks for joining us.

Thanks for having me.

It's been a pleasure.