C Refresh – Doubly Linked Lists

I worked through converting my single linked list routines to doubly linked list routines. Some of functions didn’t make sense. There was a lot of duplication between the two implementations. I kept with the unit testing using Ceedling. I did have to do a lot more debugging when my tests were failing. The swap took awhile to figure out the cases. There is unique handling for when the two nodes are next to each other. I believe swap was the most difficult. I wound up with loops when the nodes were adjacent.

I’m back to being comfortable with basic pointer usage. Looking at stack and queue data structures feels repetitious. I keep coming back to the belief that I won’t be implementing these or any data structures in a job without using a reference. While it makes no sense to think I would write a queue from scratch, I can see some benefit in just coding. It’s not just the act of writing code that helps. Being on the tools and using a debugger makes a difference.

In writing Python and Ruby code I rarely had a need for a symbolic debugger. Even writing simple applications on the Arduino was possible without a symbolic debugger. You can make a lot of progress with a reliable print statement. The symbolic debugger is viewing the local variables makes a huge difference. It would be a pain to debug by print statements for anything more than the most basic pointer usage.

Having some basic pointer work under my belt I expect to knock out the stack and queue data structures without problem. The operations are easily understood. That makes it easier compared to blindly coming up with the interface.

Stack and Queue

Thinking about those two data structures – stack and queue. They are lists of elements with specific behaviors and expected interfaces. Stack is referred to as LIFO or last-in-first-out. You push and pop things on to a stack. A stack usually has some additional operations. Peeking is used to see the top of the stack without removing the item. Also, there may be a test to see if the stack is empty.

A queue is a list with FIFO or first in first out operations. Items are added to a queue on one end and removed from the other. I believe the positions are referred to as head and tail. I can’t recall other common queue operations.