Transcript Morelist
CSCE 3110
Data Structures &
Algorithm Analysis
Rada Mihalcea
http://www.cs.unt.edu/~rada/CSCE3110
More on lists. Circular lists. Doubly linked lists.
Applications of Linked Lists
Stacks and Queues Implemented with Linked
Lists
Polynomials Implemented with Linked Lists
Remember the array based implementation?
• Hint: two strategies, one efficient in terms of space, one
in terms of running time
Operations on Linked Lists
Running time?
insert, remove
traverse, swap
How to reverse the elements of a list?
Polynomials
A( x ) a m 1 x e
m1
a m 2 x e
m 2
... a 0 x e
Representation
typedef struct poly_node *poly_pointer;
typedef struct poly_node {
int coef;
int expon;
poly_pointer next;
};
poly_pointer a, b, c;
coef
expon
link
0
Example
a 3x 2 x 1
14
a
3
8
14
2
b 8 x 3x 10 x
14
b
8
14
10
-3 10
0
null
10 6
null
1
8
6
Adding Polynomials
3
14
a
8 14
b
11 14
d
3
14
2 8
1
0
-3 10
10
6
a->expon == b->expon
2
8
1 0
a
8 14
-3 10
10
11 14
b
-3 10
d
a->expon < b->expon
6
Adding Polynomials (cont’d)
3
14
2
8
1
0
a
8
14
-3 10
10 6
b
11 14
-3 10
a->expon > b->expon
2
8
d
Adding Polynomials (cont’d)
poly_pointer padd(poly_pointer a, poly_pointer b)
{
poly_pointer front, rear, temp;
int sum;
rear =(poly_pointer)malloc(sizeof(poly_node));
if (IS_FULL(rear)) {
fprintf(stderr, “The memory is full\n”);
exit(1);
}
front = rear;
while (a && b) {
switch (COMPARE(a->expon, b->expon)) {
}
}
case -1: /* a->expon < b->expon */
attach(b->coef, b->expon, &rear);
b= b->next;
break;
case 0: /* a->expon == b->expon */
sum = a->coef + b->coef;
if (sum) attach(sum,a->expon,&rear);
a = a->next;
b = b->next;
break;
case 1: /* a->expon > b->expon */
attach(a->coef, a->expon, &rear);
a = a->next;
}
for (; a; a = a->next)
attach(a->coef, a->expon, &rear);
for (; b; b=b->next)
attach(b->coef, b->expon, &rear);
rear->next = NULL;
temp = front; front = front->next; free(temp);
return front;
Analysis
(1)
(2)
(3)
coefficient additions
0 additions min(m, n)
where m (n) denotes the number of terms in A (B).
exponent comparisons
extreme case
em-1 > fm-1 > em-2 > fm-2 > … > e0 > f0
m+n-1 comparisons
creation of new nodes
extreme case
m + n new nodes
summary
O(m+n)
Attach a Term
void attach(float coefficient, int exponent,
poly_pointer *ptr)
{
/* create a new node attaching to the node pointed to
by ptr. ptr is updated to point to this new node. */
}
poly_pointer temp;
temp = (poly_pointer) malloc(sizeof(poly_node));
if (IS_FULL(temp)) {
fprintf(stderr, “The memory is full\n”);
exit(1);
}
temp->coef = coefficient;
temp->expon = exponent;
(*ptr)->next = temp;
*ptr = temp;
Other types of lists:
Circular lists
Doubly linked lists
Circularly linked lists
circular list vs. chain
ptr
3
14
2 8
1
avail
ptr
temp
avail
...
0
Operations in a circular list
What happens when we insert a node to the front of a circular
linked list?
a
X1
X2
X3
X3
Problem: move down the whole list.
A possible solution:
X1
X2
Keep a pointer points to the last node.
a
Insertion
void insertFront (pnode* ptr, pnode node)
{
/* insert a node in the list with head
(*ptr)->next */
if (IS_EMPTY(*ptr)) {
*ptr= node;
node->next = node; /* circular link */
}
else {
node->next = (*ptr)->next; (1)
(*ptr)->next = node;
(2)
}
}
X3
X2
X1
(2)
(1)
ptr
List length
int length(pnode ptr)
{
pnode temp;
int count = 0;
if (ptr) {
temp = ptr;
do {
count++;
temp = temp->next;
} while (temp!=ptr);
}
return count;
}
Doubly Linked List
Keep a pointer to the next and the previous
element in the list
typedef struct node *pnode;
typedef struct node {
char data [4];
pnode next;
pnode prev;
}
Doubly Linked List
Keep a header and trailer pointers (sentinels)
with no content
header.prev = null; header.next = first element
trailer.next = null; trailer.prev = last element
Update pointers for every operation
performed on the list
How to remove an element from the tail of the
list ?
Doubly Linked List –
removeLast()
Running
time?
How does
this compare
to simply
linked lists?
Doubly Linked List
insertFirst
swapElements
Revisit Sparse Matrices
0 11 0
0
12 0 0
0
0
0 4 0
0
0
0
15
Previous scheme:
represent each non-NULL element as a tuple
(row, column, value)
New scheme:
each column (row): a circular linked list with a head node
Nodes in the Sparse Matrix
entry node
down
row
col
value
aij
i
j
aij
right
Linked Representation
4 4
0 2
11
1 0
12
1 1
5
2 1
-4
3 3
-15
Circular linked list
Sparse Matrix Implementation
#define MAX_SIZE 50 /* size of largest matrix */
typedef struct mnode *pmnode;
typedef struct mnode {
int row;
int col;
int value;
pmnode next, down;
};
Operations on sparse matrices