“Data Structures and Algorithm Analysis Note (II)”

ADT

Operations for the set ADT:

The List ADT

Empty list—the special list of size 0.

Operations:

The cost of these operations:

To avoid the linear cost of insertion and deletion, ensure that list is not stored contiguously.

Next pointer: Each structure contains the element and a pointer to a structure containing its successor.

The last cell’s Next pointer points to NULL (ANSI C specifies it is 0.).

A pointer variable is a variable that contains the address where some other data are stored.

Convention: the header (dummy node) is in position 0.

and (&&) operation is short-circuited: if the first half of the statement is false, the result is automatically false and the second half is not executed.

Common Errors

memory access violation or segmentation violation

A pointer variable contains a bogus address.

Common reason: failure to initialize the variable.

Whenever you do an indirection, you must make sure that the pointer is not NULL.

When and when not to use malloc to get a new cell?

You must remember that declare a pointer to a structure does not create the structure but only give enough space to hold the address where some structure might be.

The consequence of free(P): the address that P is pointing to is unchanged but the data that reside at the address are now undefined.

If you never delete from a linked list, n(malloc) = size. (n(malloc) + 1 if header is used.)

You need to keep a temporary variable to set the cell to be disposed of.

malloc(sizeof(PtrToNode)) doesn’t allocate enough space for a structure but for a pointer.

Doubly linked list: doubles the cost of insertions and deletions and simplifies deletion.

Double circularly linked list—have the last cell keep a pointer back to the first.

The Stack Model

A stack is a list with the restriction that insertions and deletions can be performed only at the end of the list, called the top.

Insert—Push;

Delete—Pop, which deletes the most recently inserted element.

LIFO—last in, first out.

Top operation—examines the element at the front of the list, returning its value.

The drawback of list implementation: calls to malloc and free are expensive, esp. in comparison to the pointer manipulation routines. (Some of this could be avoided by using a 2nd stack which is initially empty.)

Array Implementation of Stacks:

The only hazard—we need to declare an array size ahead of time.

Associated with each stack is TopOfStack, which is -1 for the empty stack.

Push—increment TopOfStack and the set Stack[TopOfStack] = X (Stack[] is the array representing the actual stack, X is the element to be pushed onto the stack);

Pop—set the return value to the Stack[TopOfStack] and then decrement TopOfStack.

BAD IDEA—use global variables and fixed names to represent or any data structure. (In real life, more than 1 stack will be used.)

No part of your code, except for stack routines, can attempt to access the array or TopOfStack variable implied by each stack.

Common Practice: Skimp on error checking in the stack routines, except where error handling is crucial.

Declaring the stack to be large enough not to overflow and ensuring that use Pop that never attempt to pop an empty stack.