Lecture 13-2 Linked List
2
Objectives
At the end of this lecture, you should be able to
• Pass structures to a function or return a structure from a function
• Explain how to use dynamic memory allocation
• Explain the linked list design and implementation
Read and Watch
• English textbook chapter 6.5, or
• For beginners, it would be easier to
read Cprogramming.com
– Lesson 15: singly linked lists in C
• Youtube video clip
– linked list in plain english
3
4
Dynamic memory allocation
• Memory on demand
• Dynamic array
– the size of the array is not known
• Dynamic allocated memory is from a heap memory limited
• It should be freed when it is not used any morememory leak bug
• C does not have garbage collection – you need to take care of it yourself
Allocate and free dynamic memory
• implemented in standard lib
5
•
• •
malloc( ), calloc( ) and realloc( ) are for memory allocations
free( ) is for de-allocation
remember to free the allocated memory
6
About allocation malloc( )
void * malloc ( size_t size)
• The malloc() function allocates size bytes and
returns a pointer to the allocated memory.
– The memory is not initialized.
• Return value
– If size is 0, or the allocation request can not be satisfied, then malloc() returns NULL
– You should always check for successful allocation • Example
int * ip;
ip = (int *) malloc ( n * sizeof (int) );
7
About allocation calloc( )
void * calloc ( size_t nmemb, size_t size)
• The calloc() function allocates memory for an array of nmemb elements of size bytes each and returns a pointer to the allocated memory.
– Total bytes: nmemb * size
• The memory is set to zero
• Return value
– It returns NULL if the request cannot be satisfied – You should always check for successful allocation
• Example int *ip;
ip = (int *) callc (n, sizeof (int) ); // how to use it?
8
Memory allocation example
• Example malloc-free.c int *x, *y;
x = (int*) malloc( sizeof (int) ); y = (int*) malloc( sizeof(int) ); *x = 1;
*y = 2;
x = y;
• free the allocated memory – free (x);
9
Self-referential structures
• A structure declaration that contains at least one variable that refers to the structure of its own kind
• With self-referential structures, complicated data structures can be realized
– linked lists – trees
– graphs
Linked list
• Linked list – A list implemented by each item having
a link to the next item.
• List – A collection of items accessible one after another, beginning at the head (the first item of
a list) and ending at the tail (the last item of a list).
A1
A2
A3
AN
10
• A linked list consists of a sequence of data
records such that in each record there is a field that contains a pointer or reference (i.e., a link) to the next record in the sequence.
Linked lists
Several different types of linked list exist:
• singly-linked lists
• doubly-linked lists
• circularly-linked lists
11
A Linked List with a header
header
A1
A2
AN
12
• A linked list can have a header node
• Header node references to the 1st node in the list
• A linked list with a header is identified by a reference (list) to the header node
• It takes one more node but makes programming easier
Node positions
header
A1
A2
AN
13
• Each node has a position in the list which denotes how far the node is from the header node
• The positions of nodes are 0, 1, 2, … – The header node is at position 0.
Linked list memory view • Linkedlistabstractionview
• Linkedlistrealmemoryview
14
Linked List Operations • Deletion
– Delete the node after some position
• Insertion
– Insert a new node to the list after some
position
15
16
How to represent a polynomial?
• A polynomial is a mathematical expression comprising a variable and several constants
• A polynomial in variable x can be written as
f(x) = a0 + a1x + a2x2 + a3x3 + … ..+ aNxN
ai are called coefficient
aixi are called a term, where xi are called exponents
• How to represent a polynomial?
– Using an array ? double a[ 1000 ];
a[0] + a[1]x + a[2]x2 + a[3]x3 + … ..+ a[99]x999 – Simple
17
How to represent a sparse polynomial?
• A sparse polynomial in variable x
f(x) = a0 + a1x + a2x2 + a3x3 + … ..+ aNxN Most ai are zero
• How to represent a sparse polynomial? – Using an array ? double a[ 1000 ];
• Simple, but it is not efficient (in both time and memory)
– Using linked list
• Only link the non-zero terms in a linked list
Example sparse polynomials
• p1(x) = 10×1000 + 5×14 + 1
• p2(x)=3×1990 -2×1492 +11x+5
• Representation in linked list
18
Sparse polynomials
• Keep the nodes sorted according to exponents • Definitions
typedef struct node * Node_ptr; struct node {
int coef;
int exp; Node_ptr next;
};
typedef Node_ptr Polynomial;
19