Understanding Doubly-linked Lists: Step by Step Development

Step 1: Understand Doubly-linked Lists

Step 1: Understand Doubly-linked Lists

Before you start on this task make sure you watched all lectures up to Lecture 15. You should have compiled, run, and understood all the code provided for pointers, dynamic data, stacks, and lists. In particular, be sure you have run, compiled and understood in detail the program linkedlist.c from Lecture 15. Your task will evolve around doubly-linked lists with a sentinel node. Thus, let us understand and visualise this concept first. In essence, a doubly-linked list is made up of a sequence of nodes where neighbouring nodes point to eachother. Each node is a structure that has a payload item x (e.g. just an int) and two pointers: back and next. The back pointer always points to the predecessor node and the next pointer always points to the successor node To represent a list in a list data structure we need two node pointers: one fixed pointer to the sentinel node (called none) to access both list ends in constant time, and one current pointer that points to a current node in the list allowing for traversals Develop in Small Steps.

 

You may want to stick to the development sequence given by the test sequence for the functions. Thus, step by step uncomment the call to its testing function first, develop and test. Remember, the more exceptions and different cases your code handles, the more liable it is to have bugs in, because there are more places for bugs to hide, and it is harder foryou to see at a glance that the code is correct. You aren't being given much opportunity for making your own implementation decisions in this closed part of the assignment. That simplifies checking correctness, and allows us to help  you more easily.