Www.cs.utsa.edu



Variations on Linked List RepresentationsHeader NodeOur representation of a linked list has been a singly linked list. There are other representations which can help to simplify insertion and deletion. Header Node - this node does not contain any actual info. It points to the first node in the list. What is the advantage of a header node?An empty list is represented by a header node which points to null. head would point to that header node.singly linked list with header node// to insert a new node after pPrecedespNew->pNext = pPrecedes->pNext;pPrecedes->pNext = pNew;// Are there any cases that can cause an issue? // Try the usual cases to check.Variations on Linked List RepresentationsCircular Linked ListWith an ordered circular linked list, the last node points to the first one. We keep a pointer to the last node instead of the first node. This is done to make it easier to insert a value less than the first node's value. There are applications where circluar lists simplify the algorithm. Example applciation:Representing the list of players in a card game as a circular linked list makes it easier to determine the next player (ie, whose turn is it). We simply advance a pointer to the current player by setting it to the next in the list. Typedefs:typedef struct NodeCL{ Element element; struct NodeCL *pNext;} NodeCL;typedef struct{ NodeCL *pLast;} CircularList;circular linked list// insert after pPrecedes// list->pLast points to the last node// check for empty listif (list->pLast == NULL){ list->pLast = pNew; pNew->pNext = pNew; // one node circular list}else{ pNew->pNext = pPrecedes->pNext; pPrecedes->pNext = pNew; // what else? what cases should we check? ??}Variations on Linked List RepresentationsDoubly Linked ListsDoubly linked lists contain pointers to the previous and next nodes. If you simply know the location of a node, it is fairly easy to delete the node. (We have special cases if we are deleting the first node or last node.)One application for a doubly linked list is the internal representation of text lines in a text editor. Typedefs:typedef struct NodeDL{ Element element; struct NodeDL *pNext; struct NodeDL *pPrev;} NodeDL;typedef struct{ NodeDL *pHead;} DoublyLinkedList;What does an empty list look like?doubly linked list// insert after pPrecedes// Assume pNew->pNext and pNew->pPrev are set to NULL // check for an empty list ??// check for inserting at the head of the list??// check for inserting at the end of the list?? Variations on Linked List RepresentationsDoubly Linked Lists With Header and Footer NodesThis a a doubly linked list with both a header and footer node. The introduction of both a header node and a footer node for a doubly linked list should simplify the cases. Typedefs:typedef struct NodeDL{ Element element; struct NodeDL *pNext; struct NodeDL *pPrev;} NodeDL;typedef struct{ NodeDL *pHeader; NodeDL *pFooter;} DoublyLinkedList;What does an empty list look like?doubly linked list with header and footer node// insert after pPrecedeswhat needs to be done? any special cases?// first, set the pointers in pNewpNew->pNext = ??pNew->pPrev = ??// set the nodes that need to point to pNew?? = pNew;?? = pNew;// For doubly linked list with header and foorter nodes, // do we really need pPrecedes???ExerciseShow a code snippet for finding where to insert a new node in a doubly linked ordered list which uses a header and a footer node.Assume:list->pHeader points to a header node.list->pFooter points to a footer node.pNew already has been allocated and contains the element.pPrecedes is used to point to the node that precedes where we want pNew inserted.// first, let's do the search for where to place pNew??// set the pointers in pNew??// set the nodes that need to point to pNew??ExerciseFor that previous exercise, change that code to use p instead of pPrecedes.// first, let's do the search for where to place pNew??// set the pointers in pNew??// set the nodes that need to point to pNew??// does the ordering of those last two statements matter??? ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download