COSC 350: Data Structures
March 4, 2009

Linked List Projects

doubly-linked
dummy nodes

Test Review Info

Your test will cover Chapter 1 through 3 and related material covered in class.  It has ten questions, most with multiple parts, and is four pages long.  While there is some overlap in the following categories, the test breaks down roughly as follows:

Three questions (16 points) ask you to describe, list, explain, or discuss ideas related to the concepts discussed in the course thus far.  All were discussed in the text and in class.

Four questions (48 points) deal with algorithmic complexity such as Big-O notation, best-average-worst case complexity, etc.

One question (15 points) deals with linked lists represented as arrays.  This is similar to the exercises we did in class last Wednesday.

Three questions (26 points) require you to write Python code.  One of those question/two parts (8 points) requires you to convert very simple code from C/C++ to Python.

Four questions (51 points) require you to be familiar with specific algorithms we discussed in class.  Specific algorithms include: linear search on unsorted data, optimized linear search on sorted data, binary search, array operations, linked list algorithms including linked lists as arrays, singly-linked lists, and doubly-linked lists.  You will not be responsible for any of the Union/Find set algorithms.

Again, some categories overlap.  

ADT's

An abstract data type is a set of values and operations on those values. The values are only accessed through the operations. An implementation of an ADT provides an opaque interface to the data.

Examples:
A stack (LIFO-last in first out) is a data stucture where items are stored on a linear list. Items can only be added or removed from the beginning (or top) of the list . Stack operations include: Create, Push, Pop, Peek, Empty, Size

A queue (FIFO-first in first out) is a data structure where items are only added to one end of a linear list and removed from the other end. Queue operations include: Create, Enqueue, Dequeue, Empty, Size

Using Python Lists

Inclass Project for Friday

You may work on this as a group in class on Friday or individually over the weekend. The final version is due on Wednesday, March 11.

Implement the ADT for a stack and a queue using a linked list approach as previously demonstrated in class. You will begin by defining a node class. Next create a stack class with the following functionality: create, push, pop, peek, empty and size. Repeat with a queue providing the functionality: create, enqueue, dequeue, empty, size. Once you have the stack, the queue should be easy to create by adapting code you already have.

This page was created by Joe Sloan.
It was last modified on or after: 11 March 2009
Send mail to: sloanjd@wofford.edu