Bt0067 c programming and data structures2

1 C Programming and Data Structures BT0067 Part-1 By Milan K Antony

2 1. What is a Pointer? Discuss the advantages of using Pointers. An object pointer, or simply pointer, is a variable that contains a memory address where an object, such as a struct or float, or an array of objects, is stored. With that memory address, the programmer can read, modify and move through the memory using a pointer. Functions that take a pointer to an external object passed in as a parameter can modify that object. When the function exits, the new value assigned to that object will persist. A function can take multiple pointers, allowing a single function to modify multiple objects with a single function call.A pointer can be used to navigate through an array of elements systematically or randomly using array notation, iteration or basic math. Using pointers for array access is faster than the more complicated implementations of similar functionality found in other languages. While such implementations are often easier to use and prevent errors, there is additional overhead that affects performance. The ability to dynamically allocate arbitrary amounts of heap memory during runtime is a technique called "dynamic memory allocation." Many earlier languages, such as Fortran, required the amount of memory allocated for structures such as arrays to be set at compile time, and the amount of memory allocated could not be changed during the running of the program. Pointers are used in C to hold the address of dynamically allocated memory.A pointer is declared by placing a star (*) between the type name and the variable name.

3 The value of an object in memory at the address held by the pointer is accessed by "dereferencing" the pointer. Dereferencing a pointer is done by putting a star (*) before the pointer name. When handling pointers to structs, a member of the struct is referenced by using an arrow (->) between the pointer name and the member name.The address of an object can be accessed by placing an ampersand (&) before the object's variable name. Passing an object's address to a function is called "pass by reference." The parameter is declared as a pointer in the function prototype. The function dereferences the parameter to modify its value, and the value will persist when the function exits. 2. Give the syntax of fread() function. When accessing files through C, the first necessity is to have a way to access the files. For C File I/O you need to use a FILE pointer, which will let the program keep track of the file being accessed. (You can think of it as the memory address of the file or the location of the file). For example: FILE *fp; To open a file you need to use the fopen function, which returns a FILE pointer. Once you've opened a file, you can use the FILE pointer to let the compiler perform input and output functions on the file. FILE *fopen(const char *filename, const char *mode);

4 In the filename, if you use a string literal as the argument, you need to remember to use double backslashes rather than a single backslash as you otherwise risk an escape character such as t. Using double backslashes escapes the key, so the string works as it is expected. Your users, of course, do not need to do this! It's just the way quoted strings are handled in C and C++. The modes are as follows: r - open for reading w - open for writing (file need not exist) a - open for appending (file need not exist) r+ - open for reading and writing, start at beginning w+ - open for reading and writing (overwrite file) a+ - open for reading and writing (append if file exists) Note that it's possible for fopen to fail even if your program is perfectly correct: you might try to open a file specified by the user, and that file might not exist (or it might be write- protected). In those cases, fopen will return 0, the NULL pointer. To close a function you can use the function int fclose(FILE *a_file); fclose returns zero if the file is closed successfully. An example of fclose is fclose(fp);

5 To work with text input and output, you use fprintf and fscanf, both of which are similar to their friends printf and scanf except that you must pass the FILE pointer as first argument. For example: FILE *fp; fp=fopen("c:test.txt", "w"); fprintf(fp, "Testing...n"); It is also possible to read (or write) a single character at a time--this can be useful if you wish to perform character- by-character input (for instance, if you need to keep track of every piece of punctuation in a file it would make more sense to read in a single character than to read in a string at a time.) The fgetc function, which takes a file pointer, and returns an int, will let you read a single character from a file: int fgetc (FILE *fp); Notice that fgetc returns an int. What this actually means is that when it reads a normal character in the file, it will return a value suitable for storing in an unsigned char (basically, a number in the range 0 to 255). On the other hand, when you're at the very end of the file, you can't get a character value--in this case, fgetc will return "EOF", which is a constnat that indicates that you've reached the end of the file. The fputc function allows you to write a character at a time--you might find this useful if you wanted to copy a file character by character. It looks like this: int fputc( int c, FILE *fp );

6 Note that the first argument should be in the range of an unsigned char so that it is a valid character. The second argument is the file to write to. On success, fputc will return the value c, and on failure, it will return EOF. Binary I/O For binary File I/O you use fread and fwrite. The declarations for each are similar: size_t fread(void *ptr, size_t size_of_elements, size_t number_of_elements, FILE *a_file); size_t fwrite(const void *ptr, size_t size_of_elements, size_t number_of_elements, FILE *a_file); Both of these functions deal with blocks of memories - usually arrays. Because they accept pointers, you can also use these functions with other data structures; you can even write structs to a file or a read struct into memory. Let's look at one function to see how the notation works. fread takes four arguments. Don't by confused by the declaration of a void *ptr; void means that it is a pointer that can be used for any type variable. The first argument is the name of the array or the address of the structure you want to write to the file. The second argument is the size of each element of the array; it is in bytes. For example, if you

7 have an array of characters, you would want to read it in one byte chunks, so size_of_elements is one. You can use the sizeof operator to get the size of the various datatypes; for example, if you have a variable int x; you can get the size of x with sizeof(x);. This usage works even for structs or arrays. Eg, if you have a variable of a struct type with the name a_struct, you can use sizeof(a_struct) to find out how much memory it is taking up. e.g., sizeof(int); The third argument is simply how many elements you want to read or write; for example, if you pass a 100 element array, you want to read no more than 100 elements, so you pass in 100. The final argument is simply the file pointer we've been using. When fread is used, after being passed an array, fread will read from the file until it has filled the array, and it will return the number of elements actually read. If the file, for example, is only 30 bytes, but you try to read 100 bytes, it will return that it read 30 bytes. To check to ensure the end of file was reached, use the feof function, which accepts a FILE pointer and returns true if the end of the file has been reached.

8 fwrite is similar in usage, except instead of reading into the memory you write from memory into a file. For example, FILE *fp; fp=fopen("c:test.bin", "wb"); char x[10]="ABCDEFGHIJ"; fwrite(x, sizeof(x[0]), sizeof(x)/sizeof(x[0]), fp); 3. Differentiate linear and nonlinear data structure. A data structure is classified into two categories: Linear and Non-Linear data structures. A data structure is said to be linear if the elements form a sequence for example Array Linked list queue etc. Elements in a nonlinear data structure do not form a sequence for example Tree Hash tree Binary tree etc. There are two ways of representing linear data structures in memory. One way is to have the linear relationship between the elements by means of sequential memory locations. Such linear structures are called arrays. The other way is to have the linear relationship between the elements represented by means of links. Such linear data structures are called linked list. Linear data structures maintain a linear structureWe can traverse either forward or backward from a nodeEg.:Stacks, Queues, Doubly/circularly/singly linked lists Non linear data structures do not maintain a

9 linear structure. It branches to more than one node and cannot be traversed in a single run Eg.: Trees, Graphs etc. 4. Discuss various Stack applications with suitable examples. Calculators employing reverse Polish notation use a stack structure to hold values. Expressions can be represented in prefix, postfix or infix notations. Conversion from one form of the expression to another form may be accomplished using a stack. Many compilers use a stack for parsing the syntax of expressions, program blocks etc. before translating into low level code. Most of the programming languages are context- free languages allowing them to be parsed with stack based machines.The calculation: 1 + 2 * 4 + 3 can be written down like this in postfix notation with the advantage of no precedence rules and parentheses needed: 1 2 4 * + 3 + The expression is evaluated from the left to right using a stack: when encountering an operand: push it  when encountering an operator: pop two operands, evaluate the result and push it.Like the following way (the Stack is displayed after Operation has taken place):

10 Inp ut Operatio n Stack (after op) 1 Push operand 1 2 Push operand 2, 1 4 Push operand 4, 2, 1 * Multiply 8, 1 + Add 9 3 Push operand 3, 9 + Add 12 The final result, 12, lies on the top of the stack at the end of the calculation. Almost all computer runtime memory environments use a special stack (the "call stack") to hold information about procedure/function calling and nesting in order to switch to the context of the called function and restore to the caller function when the calling finishes. They follow a runtime protocol between caller and callee to save arguments and return value on the stack. Stacks are an important way of supporting nested or recursive function calls. This type of stack is used implicitly by the compiler to support CALL and

11 RETURN statements (or their equivalents) and is not manipulated directly by the programmer. 5. Define List. Discuss various list operations. In computer science, a linked list is a data structure that consists of a sequence of data records such that in each record there is a field that contains a reference (i.e., a link) to the next record in the sequence. A linked list whose nodes contain two fields: an integer value and a link to the next node Linked lists are among the simplest and most common data structures; they provide an easy implementation for several important abstract data structures, including stacks, queues, hash tables, symbolic expressions, and skip lists. The principal benefit of a linked list over a conventional array is that the order of the linked items may be different from the order that the data items are stored in memory or on disk. For that reason, linked lists allow insertion and removal of nodes at any point in the list, with a constant number of operations. On the other hand, linked lists by themselves do not allow random access to the data, or any form of efficient indexing.

12 Thus, many basic operations — such as obtaining the last node of the list, or finding a node that contains a given datum, or locating the place where a new node should be inserted — may require scanning most of the list elements. Linked lists can be implemented in most languages. Languages such as Lisp and Scheme have the data structure built in, along with operations to access the linked list. Procedural languages, such as C, or object-oriented languages, such as C++ and Java, typically rely on mutable references to create linked lists. When manipulating linked lists in-place, care must be taken to not use values that you have invalidated in previous assignments. This makes algorithms for inserting or deleting linked list nodes somewhat subtle. This section gives pseudocode for adding or removing nodes from singly, doubly, and circularly linked lists in-place. Throughout we will use null to refer to an end-of-list marker or sentinel, which may be implemented in a number of ways. Singly-linked lists Our node data structure will have two fields. We also keep a variable firstNode which always points to the first node in the list, or is null for an empty list. record Node { data // The data being stored in the node

13 next // A reference to the next node, null for last node } record List { Node firstNode // points to first node of list; null for empty list } Traversal of a singly-linked list is simple, beginning at the first node and following each next link until we come to the end: node := list.firstNode while node not null { (do something with node.data) node := node.next } The following code inserts a node after an existing node in a singly linked list. The diagram shows how it works. Inserting a node before an existing one cannot be done; instead, you have to locate it while keeping track of the previous node. function insertAfter(Node node, Node newNode) { // insert newNode after node

14 newNode.next := node.next node.next := newNode } Inserting at the beginning of the list requires a separate function. This requires updating firstNode. function insertBeginning(List list, Node newNode) { // insert node before current first node newNode.next := list.firstNode list.firstNode := newNode } Similarly, we have functions for removing the node after a given node, and for removing a node from the beginning of the list. The diagram demonstrates the former. To find and remove a particular node, one must again keep track of the previous element. function removeAfter(node node) { // remove node past this one obsoleteNode := node.next node.next := node.next.next destroy obsoleteNode

15 } function removeBeginning(List list) { // remove first node obsoleteNode := list.firstNode list.firstNode := list.firstNode.next // point past deleted node destroy obsoleteNode } Notice that removeBeginning() sets list.firstNode to null when removing the last node in the list. Since we can't iterate backwards, efficient "insertBefore" or "removeBefore" operations are not possible. Appending one linked list to another can be inefficient unless a reference to the tail is kept as part of the List structure, because we must traverse the entire first list in order to find the tail, and then append the second list to this. Thus, if two linearly-linked lists are each of length n, list appending has asymptotic time complexity of O(n). In the Lisp family of languages, list appending is provided by the append procedure. Many of the special cases of linked list operations can be eliminated by including a dummy element at the front of the list. This ensures that there are no special cases for the beginning of the list and renders both insertBeginning() and removeBeginning() unnecessary. In this case, the first useful data in the list will be found at list.firstNode.next.

16 Circularly-linked list In a circularly linked list, all nodes are linked in a continuous circle, without using null. For lists with a front and a back (such as a queue), one stores a reference to the last node in the list. The next node after the last node is the first node. Elements can be added to the back of the list and removed from the front in constant time. Circularly-linked lists can be either singly or doubly linked. Both types of circularly-linked lists benefit from the ability to traverse the full list beginning at any given node. This often allows us to avoid storing firstNode and lastNode, although if the list may be empty we need a special representation for the empty list, such as a lastNode variable which points to some node in the list or is null if it's empty; we use such a lastNode here. This representation significantly simplifies adding and removing nodes with a non-empty list, but empty lists are then a special case. Algorithms Assuming that someNode is some node in a non-empty circular singly-linked list, this code iterates through that list starting with someNode: function iterate(someNode) if someNode ≠ null

17 node := someNode do do something with node.value node := node.next while node someNode≠ Notice that the test "while node someNode" must be at the≠ end of the loop. If it were replaced by the test "" at the beginning of the loop, the procedure would fail whenever the list had only one node. This function inserts a node "newNode" into a circular linked list after a given node "node". If "node" is null, it assumes that the list is empty. function insertAfter(Node node, Node newNode) if node = null newNode.next := newNode else newNode.next := node.next node.next := newNode Suppose that "L" is a variable pointing to the last node of a circular linked list (or null if the list is empty). To append "newNode" to the end of the list, one may do insertAfter(L, newNode) L := newNode

18 To insert "newNode" at the beginning of the list, one may do insertAfter(L, newNode) if L = null L := newNode Linked lists using arrays of nodes Languages that do not support any type of reference can still create links by replacing pointers with array indices. The approach is to keep an array of records, where each record has integer fields indicating the index of the next (and possibly previous) node in the array. Not all nodes in the array need be used. If records are also not supported, parallel arrays can often be used instead. As an example, consider the following linked list record that uses arrays instead of pointers: record Entry { integer next // index of next entry in array integer prev // previous entry (if double-linked) string name real balance } By creating an array of these structures, and an integer variable to store the index of the first element, a linked list can be built:

19 integer listHead Entry Records[1000] Links between elements are formed by placing the array index of the next (or previous) cell into the Next or Prev field within a given element. For example: Index Ne xt Pr ev Name Balan ce 0 1 4 Jones, John 123.45 1 -1 0 Smith, Joseph 234.56 2 (listHead) 4 -1 Adams, Adam 0.00 3 Ignore, Ignatius 999.99 4 0 2 Another, Anita 876.54 5 6 7 In the above example, ListHead would be set to 2, the location of the first entry in the list. Notice that entry 3 and 5 through 7 are not part of the list. These cells are available

20 for any additions to the list. By creating a ListFree integer variable, a free list could be created to keep track of what cells are available. If all entries are in use, the size of the array would have to be increased or some elements would have to be deleted before new entries could be stored in the list. The following code would traverse the list and display names and account balance: i := listHead while i >= 0 { '// loop through the list print i, Records[i].name, Records[i].balance // print entry i := Records[i].next } 6. What is a Structure? Explain with examples. Arrays are used to store large set of data and manipulate them but the disadvantage is that all the elements stored in an array are to be of the same data type. If we need to use a collection of different data type items it is not possible using an array. When we require using a collection of different data items of different data types we can use a structure. Structure is a method of packing data of different types. A structure is a convenient method of handling a group of related data items of different data types.

21 structure definition: general format: struct tag_name { data type member1; data type member2; ... ... } Example: struct lib_books { char title[20]; char author[15]; int pages; float price; }; the keyword struct declares a structure to holds the details of four fields namely title, author pages and price. These are members of the structures. Each member may belong to different or same data type. The tag name can be used to define objects that have the tag names structure. The structure we just declared is not a variable by itself but a template for the structure.

22 We can declare structure variables using the tag name any where in the program. For example the statement, struct lib_books book1,book2,book3; declares book1,book2,book3 as variables of type struct lib_books each declaration has four elements of the structure lib_books. The complete structure declaration might look like this struct lib_books { char title[20]; char author[15]; int pages; float price; }; struct lib_books, book1, book2, book3; structures do not occupy any memory until it is associated with the structure variable such as book1. the template is terminated with a semicolon. While the entire declaration is considered as a statement, each member is declared independently for its name and type in a separate statement inside the template. The tag name such as lib_books can be used to declare structure variables of its data type later in

23 the program. We can also combine both template declaration and variables declaration in one statement, the declaration struct lib_books { char title[20]; char author[15]; int pages; float price; } book1,book2,book3; Initializing structure: Like other data type we can initialize structure when we declare them. As for initalization goes structure obeys the same set of rules as arrays we initalize the fields of a structure by the following structure declaration with a list containing values for weach fileds as with arrays these values must be evaluate at compile time. Example: Struct student newstudent { 12345, “kapildev”

24 “Pes college”; “Cse”; 19; }; 7. What are the different modes used to open a file? The file stream constructor takes a second argument, the open mode, that allows such variations to be specified. Here is an example that creates a file stream object Str, connects it to the external file named "inout.txt", and opens it for reading and for writing at the end of the file: std::fstream Str("inout.txt", std::ios_base::in | std::ios_base::out | std::ios_base::app); Input (and output) file streams always have the in (or out) open mode flag set implicitly. An output file stream, for instance, knows that it is in output mode and you need not set the output mode explicitly. Instead of writing: std::ofstream Str("out.txt", std::ios_base::out | std::ios_base::app); you can simply say: std::ofstream Str("out.txt", std::ios_base::app);

25 Bidirectional file streams, on the other hand, do not have the flag set implicitly. This is because a bidirectional stream does not have to be in both input and output mode in all cases. You might want to open a bidirectional stream for reading only or writing only. Bidirectional file streams therefore have no implicit input or output mode. You must always set a bidirectional file stream's open mode explicitly. Each file maintains a single file position that indicates the position in the file where the next byte will be read or written. When a file is opened, the initial file position is usually at the beginning of the file. The open modes std::ios_base::ate (meaning at end) and std::ios_base::app (meaning append) change this default to the end of the file. There is a subtle difference between ate and app mode. If the file is opened in append mode, all output to the file is done at the current end of the file, regardless of intervening repositioning. Even if you modify the file position to a position before the file's end, you cannot write there. With ate mode, you can navigate to a position before the end of file and write to it. If you open an already existing file for writing, you usually want to overwrite the content of the output file. The open mode std::ios_base::trunc (meaning truncate) has the effect of discarding the file content, in which case the initial file length is set to 0. Therefore, if you want to replace a file's content

26 rather than extend the file, you must open the file in std::ios_base::out | std::ios_base::trunc. Note that the file position is at the beginning of the file in this case, which is exactly what you expect for overwriting an output file. he effect of combining these open modes is similar to the mode argument of the C library function fopen(name,mode). Table 33 gives an overview of all permitted combinations of open modes for text files and their counterparts in C stdio. Combinations of modes that are not listed in the table (such as both trunc and app) are invalid, and the attempted open() operation fails. Table 33: Open modes and their C stdio counterparts Open Mode C stdio Equivalent Effect in "r" Open text file for reading only out|trunc out "w" Truncate to 0 length, if existent, or create text file for writing only out|app "a" Append; open or create text file only for writing at end of file in|out "r+" Open text file for update (reading and

27 writing) in|out| trunc "w+" Truncate to 0 length, if existent, or create text file for update in|out|app "a+" Append; open or create text file for update, writing at end of file When you open a file, you must specify how it is to be opened. This means whether to create it from new, overwrite it and whether it's text or binary, read or write and if you want to append to it. This is done using one or more file mode specifiers which are single letters "r", "b", "w", "a" and + (in combination with the other letters). "r" - Opens the file for reading. This fails if the file does not exist or cannot be found. "w" - Opens the file as an empty file for writing. If the file exists, its contents are destroyed. "a" - Opens the file for writing at the end of the file (appending) without removing the EOF marker before writing new data to the file; this creates the file first if it doesn't exist. Adding + to the file mode creates three new modes: "r+" Opens the file for both reading and writing. (The file must exist.) "w+" Opens the file as an empty file for both reading and writing. If the file exists, its contents are destroyed.

28 "a+" Opens the file for reading and appending; the appending operation includes the removal of the EOF marker before new data is written to the file and the EOF marker is restored after writing is complete; creates the file first if it doesn't exist. 8. Explain various levels in Data Structure. The primary distinction between a class and a structure is that a class can have both variables and methods, while a structure can have only variables. A structure type definition in C looks like the following. struct Point { int x; int y; }; /* The semicolon here is required! */ Here, we've defined a type called struct Point. In C, struct is part of the type name for every structure defined. (C++ makes this keyword optional, and so the type might just be called Point. But we're talking about C now.) Each struct Point variable has two sub-variables (called fields), x and y. So you can write the following (which does nothing interesting except illustrate a C structure's use). int main() { struct Point p;

29 p.x = 50; p.y = 100; return 0; } When you pass a structure as a parameter, you should pass a pointer to the structure, not the structure itself. The reason is that structures tend to contain lots of data, and copying all of the fields into the parameter variable is inefficient. #include <math.h> double distanceToOrigin(struct Point *p) { return sqrt((*p).x * (*p).x + (*p).y * (*p).y); } In fact, the (*ptr).field construct is so common that C includes a shortcut for it: The arrow operator allows you to write ptr->field in place of (*ptr).field. Thus, the following definition is equivalent. #include <math.h> double distanceToOrigin(struct Point *p) { return sqrt(p->x * p->x + p->y * p->y); } 9. Define Stack. Explain various Stack operations.

30 In computer science, a stack is a last in, first out (LIFO) abstract data type and data structure. A stack can have any abstract data type as an element, but is characterized by only two fundamental operations: push and pop. The push operation adds to the top of the list, hiding any items already on the stack, or initializing the stack if it is empty. The pop operation removes an item from the top of the list, and returns this value to the caller. A pop either reveals previously concealed items, or results in an empty list. stack is an abstract data type and data structure based on the principle of Last In First Out (LIFO). Stacks are used extensively at every level of a modern computer system. For example, a modern PC uses stacks at the architecture level, which are used in the basic design of an operating system for interrupt handling and operating system function calls. Among other uses, stacks are used to run a Java Virtual Machine, and the Java language itself has a class called "Stack", which can be used by the programmer. The stack is ubiquitous. There are 4 main widely used stack operations. Operations:  POP - increase stack pointer and return top element  PUSH - putting element into stack's top  TOP - returns data of top element on stack  LENGTH/SIZE - returns number of elements inside stack

31 A typical stack is an area of computer memory with a fixed origin and a variable size. Initially the size of the stack is zero. A stack pointer, usually in the form of a hardware register, points to the most recently referenced location on the stack; when the stack has a size of zero, the stack pointer points to the origin of the stack. The two operations applicable to all stacks are:  a push operation, in which a data item is placed at the location pointed to by the stack pointer, and the address in the stack pointer is adjusted by the size of the data item;  a pop or pull operation: a data item at the current location pointed to by the stack pointer is removed, and the stack pointer is adjusted by the size of the data item. There are many variations on the basic principle of stack operations. Every stack has a fixed location in memory at which it begins. As data items are added to the stack, the stack pointer is displaced to indicate the current extent of the stack, which expands away from the origin (either up or down, depending on the specific implementation). For example, a stack might start at a memory location of one thousand, and expand towards lower addresses, in which case new data items are stored at locations ranging below 1000, and the stack pointer is decremented each time a new item is

32 added. When an item is removed from the stack, the stack pointer is incremented. Stack pointers may point to the origin of a stack or to a limited range of addresses either above or below the origin (depending on the direction in which the stack grows); however, the stack pointer cannot cross the origin of the stack. In other words, if the origin of the stack is at address 1000 and the stack grows downwards (towards addresses 999, 998, and so on), the stack pointer must never be incremented beyond 1000 (to 1001, 1002, etc.). If a pop operation on the stack causes the stack pointer to move past the origin of the stack, a stack underflow occurs. If a push operation causes the stack pointer to increment or decrement beyond the maximum extent of the stack, a stack overflow occurs. Some environments that rely heavily on stacks may provide additional operations, for example:  Dup(licate): the top item is popped, and then pushed again (twice), so that an additional copy of the former top item is now on top, with the original below it.  Peek: the topmost item is inspected (or returned), but the stack pointer is not changed, and the stack size does not change (meaning that the item remains on the stack). This is also called top operation in many articles.  Swap or exchange: the two topmost items on the stack exchange places.

33  Rotate: the n topmost items are moved on the stack in a rotating fashion. For example, if n=3, items 1, 2, and 3 on the stack are moved to positions 2, 3, and 1 on the stack, respectively. Many variants of this operation are possible, with the most common being called left rotate and right rotate. Stacks are either visualized growing from the bottom up (like real-world stacks), or, with the top of the stack in a fixed position (see image [note in the image, the top (28) is the stack 'bottom', since the stack 'top' is where items are pushed or popped from]), a coin holder, a Pez dispenser, or growing from left to right, so that "topmost" becomes "rightmost". This visualization may be independent of the actual structure of the stack in memory. This means that a right rotate will move the first element to the third position, the second to the first and the third to the second. Here are two equivalent visualizations of this process: 10. Explain Singly Linked List with a neat diagram. The singly-linked list is the most basic of all the linked data structures. A singly-linked list is simply a sequence of dynamically allocated objects, each of which refers to its successor in the list. Despite this obvious simplicity, there are myriad implementation variations. Figure shows several of the most common singly-linked list variants.

34 Figure: Singly-linked list variations. 7 (a). Each element of the list refers to its successor and the last element contains the null reference. One variable, (a), is used to keep track of the list. The basic singly-linked list is inefficient in those cases when we wish to add elements to both ends of the list. While it is easy to add elements at the head of the list, to add elements at the other end (the tail ) we need to locate the last element. If the basic basic singly-linked list is used, the entire list needs to be traversed in order to find its tail. (b) shows a way in which to make adding elements to the tail of a list more efficient. The solution uses a second variable, tail , which refers to the last element of the list. Of course,

35 this time efficiency comes at the cost of the additional space used to store the variable tail. The singly-linked list labeled (c) in illustrates two common programming tricks. There is an extra element at the head of the list called a sentinel . This element is never used to hold data and it is always present. The principal advantage of using a sentinel is that it simplifies the programming of certain operations. For example, since there is always a sentinel standing guard, we never need to modify the head variable. Of course, the disadvantage of a sentinel such as that shown in (c) is that extra space is required, and the sentinel needs to be created when the list is initialized. The list (c) is also a circular list . Instead of using a null reference to demarcate the end of the list, the last element of the list refers to the sentinel. The advantage of this programming trick is that insertion at the head of the list, insertion at the tail of the list, and insertion at an arbitrary position of the list are all identical operations. Of course, it is also possible to make a circular, singly-linked list that does not use a sentinel. shows a variation in which a single variable is used to keep track of the list, but this time the variable, tail, refers to the last element of the list. Since the list is circular in this case, the first element follows the last element of the list. Therefore, it is relatively simple to insert both at the head and at the tail of this list. This

36 variation minimizes the storage required, at the expense of a little extra time for certain operations. illustrates how the empty list (i.e., the list containing no list elements) is represented for each of the variations given . Notice that the sentinel is always present in list variant (c). On the other hand, in the list variants which do not use a sentinel, the null reference is used to indicate the empty list.

Bt0067 c programming and data structures2

More Related Content

What's hot

Viewers also liked

Similar to Bt0067 c programming and data structures2

More from Techglyphs

Recently uploaded

Bt0067 c programming and data structures2