Lect 7

CSE211 Lecture Notes – 2004/2005-II

CSE 211: Data Structures Lecture Notes VII by Ender Ozcan, Sebnem Baydere LINKED LISTS In the previous lectures we have seen the representation of ordered lists using an array and sequential mapping. These representations had the property that successive nodes of the data object were stored in a fixed distance apart. For example : If the element aij of a table was stored at location Lij then a ij+1 was at the location Lij+c for a known constant c. Problems : • The sequential storage schemes are adequate if one wished to access for given node in a table, insertion or deletions of nodes within a stack or queue. However insertions or deletions of arbitrary elements become expensive. • If we have several ordered lists of varying sizes, by storing each list in a different array of maximum size, storage may be wasted. Additionally, in several cases we will need more than accessing the top item as in the stacks or inserting to the tail and accessing the head (queues). We need more general operations such as finding or removing any item in the list, inserting a new item at any point. Solution: The problem of data movement in sequential representations may be solved by using linked representations and dynamic memory allocation. Unlike a sequential representation where successive items of a list are located a fixed distance apart, in a linked representation each item of the list may be placed anywhere in memory. To access elements in the list in the correct order, with each element we store the location of the next element in that list. Associated with each data item in a linked representation there is a pointer to the next item. In modern languages providing built- in support for linked structures, the compiler associates a special storage with an object program which it leaves initially unassigned to any program variable. This area is usually called the heap or the dynamic storage pool. There is a heap manager program for the allocation of this storage from the heap at execution time. The allocated space can be referenced using pointers. Remember that pointer is just an abstraction for a machine address. Linked List Building Blocks: A linked list is an ordered sequence of elements called nodes. A list has a beginning, or head and an end , or tail. Every node on the list is the same type, although that type can take different forms. A central property of linked lists is their dynamic nature. Nodes can be added to or removed from a list at any time. Because the number of nodes cannot be predicted before run time. You should use pointers, rather than arrays, to achieve an efficient and reliable implementation.

CSE211 Lecture Notes – 2004/2005-II

Nodes Each node of a list consists of two parts. The first part holds the data. The first part holds the data. The data can be a simple variable or, more generally a structure ( or pointer to a structure) of some type. The second part is a pointer that indicatesthe location of the next node of the list. The nodes of a list can be implemented by a recursive structure. Consider the case where a single integer varaible is to be stored at each node of the list.

struct simplenode { int item; struct simplenode *next;}; typedef struct simplenode simple_t;

class simplenode { int item; simplenode *next; ... };

In this case the integer variable item holds the actual data in each node, and the pointer variable next holds the address of the next node. item

next

In general, the item part may contain several pieces of data defined in a strcut type. We can generalize the list definition above as:

struct generalList { infoType item; struct generalList *next; }; typedef struct generalList glist_t;

template class generalList { infoType item; generalList *next; ... };

We assume that info_type has been defined before. The problem with this kind of implementation is that for each type of list you must assign the individual components one by one when transfering information to and from the nodes. Ex. if s1 and s2 are both structures. In C, you cannot say s1=s2. You can assign only a single structure component in each statement. You can however write a function called assign and call it whenever needed. assign(s1,s2); info_type s1,s2; { /* assign each component of struct 2 to struct 1 */ }

CSE211 Lecture Notes – 2004/2005-II

This function carries out the detailed transfer of the individual structure components from 21 to s1. You can then build a series of generic list manipulation functions that use assign. The problem with this approach is the performance. You will be transfering data among different memory locations. However you only need to transfer the address of the blocks of data corresponding to the structures. Solution: use a structure composed of a pair of pointers. The first pointer points to the data, the second points to the next item.

struct node { infoType * item; struct node *next; }; typedef struct node node_type;

item

template class Node { infoType * item; Node *next; ... };

next

Manipulation of Linked Lists The manipulation of linked lists involves allocating storage for nodes (in C using malloc) and assigning data and/or pointers so that the list is properly formed. List's boundary conditions must be decided. In other words how are the head and tail of a list will be indicated. For the representation of the tail NULL pointer can be used (show it on the example) but for the head different approaches are possible. • • •

Define a pointer variable to hold the starting adress of the list. Define a special header node with the same structure. In this case the next element of the header node indicates the beginning of the list. (item part is unused - a small waste) Define a header node with a separate structure which holds exactly the information required. In this case other information related to the list such as number of elements in the list can be added to the header.

CSE211 Lecture Notes – 2004/2005-II

struct head{ int length; node_type *first, *last; } typedef struct head head_type;

template class LinkedList{ int length; Node *first,*last; int insert(infoType *data) int append(infoType *data) int delete(Node *ptr) … }

If a symmetric header is used:

If a custom head is used: (length, last, first)

Operations on One-way Lists and their Implementations Allocating Memory When an array is defined, storage is automatically allocated by the compiler. When you are using pointers, however you must allocate the storage. In C, two standard library functions are provided for this purpose. malloc--- allocates a single piece of storage space and leaves it uninitialized calloc() -- allocates entire set of storage locations and fills the total storage with zero char *malloc(size) -------- allocates size number of bytes and returns a pointer to the first Although it returns a character pointer it can be used to allocate space for any type of element not just characaters by applying a simple type casting Size is the value returned by the sizeof operator • sizeof expression sizeof(type name)

CSE211 Lecture Notes – 2004/2005-II

•

Type casting : new_variable = (type_name) old_variable

We will define a fucntion called MALLOC and use it in the algorithms

#define MALLOC(x) float *place;

((x

*) malloc(sizeof(x)))

/* A float pointer */

place = (float *) malloc (sizeof(float)); place = MALLOC(float); place = new float[1];

Creating a new list 1. allocate memory for header node 2. set length to 0 3. set first and last nodes to NULL head_type *create(){ head_type *new_node; if (new _node = MALLOC(head_type) ) { new_node ->length = 0; new_node -> first = new_node -> last = NULL; } return(new _node); /* adress of new list */ } Inserting a new element at the beginning of a list A) Create a storage for the new node

1. Create storage for a new list node; 2. Assign appropriate pointer values to the new node 3. Assign new values to the components of the header node. Example given at the lecture. /* create a storage for the new node */ node_type *alloc_node(info_type * val, node_type * ptr) { node_type *new_node; if (new_node = MALLOC(node_type)) { new_node -> item = val; new_node -> next = ptr;} return(new_node); }

CSE211 Lecture Notes – 2004/2005-II

B) Inserting a new element at the beginning of a list 1. Allocate memory for the new node and set it (if possible) 2. Link the first pointer of header to the new node (?last) 3. Increment length by 1 int insert_node (info_type *data, head_type *list) { node_type *new_node; if (new _node = alloc_node(data, list->first)) { list->first = new_node; /* link in new node if (list->length == 0) /* if this is the first node list-> last = new_node; /* set last pointer to new list->length ++; return(1); /* success */ } else return(0); /* error */ }

*/ */ */

Appending a new item to the end of a list Another common operation appends a new item to the end of a list. The before and after situations are diagrammed below. You know where to find the current last node in the list by means of the last pointer, which is maintained in the header block. Thus you only need to allocate me mory for a new node and rearrange pointers accordingly. int append (info_type *data, head_type *list) { node_type *new_node;/* append data to end of list */ if (new_node=alloc_node(data, NULL){ /* allocation OK, append data item */ if (list -> length) /* if the list is not empty */ list->last->next = new_node; /* link in new node */ else /* otherwise */ list->first = new_node; /* set first pointer to new */ list -> last = new_node; /* update last pointer */ list -> length++; /* update list length */ return(1); /* success */ } else /* allocation problem */ return(0); /* error*/ }

BEFORE:

AFTER:

CSE211 Lecture Notes – 2004/2005-II

Deleting Nodes Study yourself.

Doubly Linked Lists Finding the predecessor of a node in a one-way list requires a linear search. We can add a pointer to its predecessor, to each node. It will consume more space but search will be faster. Sometimes you may need to move through a list from the end to the beginning by following pointers. Inorder to be able to do this we can define two pointers in each node; One points to the next and one points to the previous node.

Length

Last

First

Previous

(HEADER )

Item

Next

(NODE)

(a doubly linked list) For doubly linked lists, you need to develop a new set of routines that are analogous to those for ordinary (singly linked) lists. The function to create a new doubly linked list is nearly the same as that for singly linked lists, in that you have to change only the data types of the header pointers. Let us first define the doubly linked list node: struct doubly{ info_type *item struct doubly *next, *prev; } typedef struct doubly doubly_type;

template class doubly{ infoType *item doubly *next, *prev; ... }

Header Node: It does not need to change. We only need to change the type of pointers from node_type to doubly_type.

CSE211 Lecture Notes – 2004/2005-II

Operations on Doubly Linked Lists (Two-Way Lists) Create operation head_db_type *create_db() { head_db_type *new_node; /* attempt to allocate memory */ if (new_node =MALLOC(head_db_type)) { /* allocation OK, initialize the values */ new_node -> length = 0; new_node -> first = NULL; new_node ->last = NULL; } /* return the address of the new list */ return(new_node); }

DoublyLinkedList(){ first = NULL; last = NULL; length = 0; }

We also need to write a function which creates a new node. /* create a storage for the new doubly linked node */ doubly_type *alloc_db_node(val, prev, next) info_type *val; doubly_type *prev, *next;{ doubly_type *new_node; if(new_node=MALLOC(doubly_type)) { new_node -> item = val; new_node -> prev = prev; new_node -> next = next; } return(new_node); }

doubly( info_type *val, doubly *prv, doubly *nxt) { item = val; prev = prv; next = nxt; }

Using this function we can write insert and append functions: /* Insert node at the beginning of a doubly linked list */

CSE211 Lecture Notes – 2004/2005-II

int insert_dbl ( info_type *data, head_db_type *list ){ doubly_type *new_node; if (new_node = alloc_db_node(data, NULL, list->first)) { if (list->length == 0) /* if this is the first node */ list->last = new_node; /* set the last pointer to the new */ else { /* if not the first node link it in */ list->first->prev = new_node; /* set prev field of first node */ list->first = new_node; /*set the first pointer to the new */ } list->length++; return(1); /* success */ }else return(0); } /* error */

Previous field of the first node is 0 Next field of the last node is 0 (before insertion)

(after insertion) Append a node to the end of the list Home study-- do it yo urself

CSE211 Lecture Notes – 2004/2005-II

Deleting first node from a doubly linked list We assume that before calling the delete function you have checked the length of the list. The function retiurns the data field of the deleted node and frees the memory used by this Node. info_type *del_dbl(head_db_type *list){ doubly_type *temp; info_type *data; /* delete first node */ temp= list->first; /* save the pointer */ data = temp->item; /* save the data */ list->first = temp->next; /* reassign the first pointer */ list->length--; /* update list length */ if (list->length ) /* if new list is not empty */ list->first->prev = NULL; /* set prev field of first item to NULL*/ else /* otherwise */ list->last = NULL; /* set last pointer to NULL */; free((char )temp); /* free node storage */ return(data); }

(before deletion )

(after deletion)