Transcript MoreLists
CSCE 3110
Data Structures &
Algorithm Analysis
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->link;
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)
Other types of lists:
Circular lists
Doubly linked lists
Circularly linked lists
circular
ptr
3
14
2 8
1
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
Transpose
Addition
Multiplication