ROB 599: Programming for Robotics: Class 6

Announcements!

  1. Next Tuesday we will have several teaching consultants from the Engineering Center for Research, Learning, and Teaching come to our class to observe and ask questions about the class. I will be out of the room while they are talking with you, so please respond fully and candidly! Afterwards, they will write a report for me to help improve the class and my teaching. Any information you give them will be completely anonymous in their report.
  2. I made a piazza post about new due dates last week, but I think it didn’t up being visible enough:

    Hello class! I have been thinking about when to make class and homework assignments due so that we all can better focus our time.

    1. Starting with class6 on Wednesday next week, you will have two days, until Friday at 6:00pm to finish those in-class assignments. For Tuesday you will have until Thursday at 6:00pm. The normal late policy of 1% per hour holds. The idea is that the in-class assignments are less important than homework, and I don’t want homework to get less time and effort because of it. Remember that homework points are worth a lot more for your grade! See the syllabus for how grades work between class assignments and homework.
    2. Homework2 will be due Saturday October 5th at 6:00pm, a bit more than a week after the last class in that section of the syllabus. This should give you a lot more time to finish it, and hopefully not completely cannibalize the next section of the class! These two weeks might seem like a while, but you need working collision code for this homework, and I highly recommend starting on it as early as possible.
    3. If you have any questions or concerns about these due dates, please let me know! I am open to considering alternatives that will help everyone learn as much as possible.
  3. I just added start code for class6. You will need to run git pull upstream master to get it!

In-class problem 1: linked

In this problem we will implement a doubly linked list.

From the wikipedia article:

A linked list is a linear collection of data elements, whose order is not given by their physical placement in memory. Instead, each element points to the next.

As each node in a linked list is independent in memory, each one will have to be malloc’ed and freed individually. In addition, in a doubly linked list, each node not only maintains a pointer to the next node after it, but also the previous node. In implementing this data structure we have to be very careful to keep all the next and previous pointers consistent.

Each node will have three fields: next, prev, and value.
The list overall will keep track of both the start and end nodes.

We will implement the following operations, although more are possible:

  • push_start
  • push_end
  • pop_start
  • pop_end

In addition, you will also need to implement some mechanism to destroy your list, since we can’t be leaking memory!

We are providing some base code that will read the push and pop commands from a file. And whenever we pop a value off the linked list, we print it out.

For a file of commands:

push_start 1
push_start 2
pop_start
pop_start
2
1

And for:

push_start 1
push_start 2
pop_end
pop_end
1
2

And:

push_start 1
push_start 2
push_end 3
push_end 4
push_end 5
pop_start
pop_start
pop_start
pop_end
pop_end
2
1
3
5
4