DOC PREVIEW
UCF COP 3502H - Linked Lists

This preview shows page 1-2-3-24-25-26 out of 26 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1 Linked Lists2Static and Dynamic Variables • Static Variables: − They are created during compilation. (Fixed memory is reserved for them.) − They cannot be allocated / de-allocated during the execution of the program. − Names are associated with them. int x; char y[10]; int z[100]; • Dynamic Variables: − They are created (allocated) and de-allocated during the execution of the program. − no names are associated with them. The only way to access them is to use pointers. − They don’t exist during compilation. Once they are created they contain data and must have a type like any other variable. Thus we can talk about creating a new dynamic variable of type x and setting a pointer to point to it, or returning a dynamic variable of type x to the system (de-allocation).3A Conceptual View of Memory PROGRAM MEMORY RAM main called and standard functions global program heap system stack DATA MEMORY4Dynamic Data For example: • We must maintain a list of data • At some moments, the list is small, so we want to use only a little memory • At other moments, the list is larger, so we need to use more memory • Declaring variables in the standard way won’t work here because we don’t know how many variables to declare • We need a way to allocate and de-allocate data dynamically (i.e., on the fly)5Dynamic Memory Allocation Creating and maintaining dynamic data structures requires dynamic memory allocation – the ability for a program to obtain more memory space at execution time to hold new values, and to release space no longer needed. In C, functions malloc and free, and operator sizeof are essential to dynamic memory allocation. • Unary operator sizeof is used to determine the size in bytes of any data type. e.g. sizeof(double) sizeof(int) • Function malloc takes as an argument the number of bytes to be allocated and return a pointer of type void * to the allocated memory. (A void * pointer may be assigned to a variable of any pointer type. ) It is normally used with the sizeof operator.6Let us say we want to store an integer pointed by nump, a character pointed by letp and a user defined structure of type planet_t pointed by planetp. This will be done as follows: int *nump; char *letp; planet_t *planetp; user defined structure type nump = (int *)malloc(sizeof (int)); letp = (char *)malloc(sizeof (char)); planetp = (planet_t *)malloc(sizeof (planet_t)); nump will now point to one byte of integer location in memory. Letp will now point to one location in memory to hold a character Planetp will now point to a group of locations in memory sufficient to hold the information needed for a structure of type planet_t.7An example: struct node{ int data; struct node *next; }; struct node *ptr; ptr = (struct node *) malloc(sizeof(struct node)); • Function free de-allocates memory- i.e. the memory is returned to the system so that the memory can be reallocated in the future. e.g. free(ptr); ? ? ptr ptr ?8Linked Lists • It is an important data structure. • An abstraction of a list: i.e. a sequence of nodes in which each node is linked to the node following it. • Lists of data can be stored in arrays, but linked lists provide several advantages: Arrays − In an array each node (element) follows the previous one physically (i.e. contiguous spaces in the memory) − Arrays are fixed size: either too big (unused space ) or not big enough (overflow problem) − Maximum size of the array must be predicted which is sometimes impossible. − Inserting and deleting elements into an array is difficult. Have to do lot of data movement, if in array of size 100, an element is to be inserted after the 10th element, then all remaining 90 have to be shifted down by one position.9Linked Lists − Linked lists are appropriate when the number of data elements to be represented in the data structure are not known in advance. − Linked lists are dynamic, so the length of a list can increase or decrease as necessary. − A linked list is a collection of nodes, each node containing a data element. − Each node does not necessarily follow the previous one physically in the memory. Nodes are scattered at random in memory. − Insertion and Deletion can be made in Linked lists , by just changing links of a few nodes, without disturbing the rest of the list. This is the greatest advantage. − But getting to a particular node may take large number of operations, as we do not know the address of any individual node . − Every node from start needs to be traversed to reach the particular node.10A simple Node Structure A node in a linked list is a structure that has at least two fields. One of the fields is a data field; the other is a pointer that contains the address of the next node in the sequence. struct list { int data; struct list *next; } The pointer variable next is called a link. Each structure is linked to a succeeding structure by way of the field next. The pointer variable next contains an address of either the location in memory of the successor struct list element or the special value NULL. data next11More examples of Nodes A node with one data field: struct node{ int number; struct node * link; }; A node with 3 data fields: struct student{ char name[20]; int id; double grdPts; struct student *next_student; }; A structure in a node: struct person{ char name[20]; char address[30]; char phone[10]; }; struct person_node{ struct person data; struct person_node *next; }; name id grdPts next_student number link name address phone data next12 A simple Linked List • The head pointer addresses the first node of the list, and each node points at its successor node. • The last node has a link value NULL. Empty List No data elements, no nodes. So Head points to NULL. Empty Linked list is a single pointer having the value of NULL. pHead = NULL; head head13 Basic Linked List Operations 1. Add a node 2. Delete a node 3. Looking up a node 4. List Traversal (e.g. Counting nodes) Add a Node There are four steps to add a node to a linked list: 1. Allocate memory for the new node. 2. Determine the insertion point (you need to know only the new node’s predecessor (pPre) 3. Point the new


View Full Document

UCF COP 3502H - Linked Lists

Download Linked Lists
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Linked Lists and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Linked Lists 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?