In eduladder you can Ask,Answer,Listen,Earn and Download Questions and Question papers.

Watch related videos of your favorite subject.

Connect with students from different parts of the world.

Apply or Post Jobs, Courses ,Internships and Volunteering opportunity. For FREE

See Our team

Wondering how we keep quality?

Got unsolved questions? Ask Questions

GATE
GMAT
CBSE
NCERT
Career
Interview
Railway
UPSC
NID
NIFT-UG
NIFT-PG
PHP
AJAX
JavaScript
Node Js
Shell Script
Research

You are here:Open notes-->VTU-->Data-structure-with-C-10CS35-unit-4

**Data structure with C 10CS35 unit 4**

# UNIT - 4 LINKED LISTS

**4.1 Singly Linked lists and Chains**

Drawbacks of stacks and queues. During implementation, overflow occurs. No simple solution exists for more stacks and queues. In a sequential representation, the items of stack or queue are implicitly ordered by the sequential order of storage.

If the items of stack or queue are explicitly ordered, that is, each item contained within itself the address of the next item. Then a new data structure known as linear linked list. Each item in the list is called a node and contains two fields, an information field and a next address field. The information field holds the actual element on the list. The next address field contains the address of the next node in the list. Such an address, which is used to access a particular node, is known as a pointer.The null pointer is used to signal the end of a list. The list with no nodes empty listor null list. The notations used in algorithms

are:If p is a pointer to a node, node(p) refers to the node pointed to by p.

**Singly linked list:**Singly linked lists contain nodes which have a data field as well as a next field, which points to the next node in line of nodes. A singly linked list whose nodes contain two fields: an integer value and a link to the next node

**Doubly linked list**: Doubly linked list In a doubly linked list, each node contains, besides the next-node link, a second link field pointing to the previous node in the sequence. The two links may be called forward(s) and backwards, or next and prev(previous).

A technique known as XOR-linking allows a doubly linked list to be implemented using a single link field in each node. However, this technique requires the ability to do bit operations on addresses, and therefore may not be available in some high-level language

information portion of the node that follows node(p) inthe list.

A linked list (or more clearly, "singly linked list") is a data structure that consists of a sequence of nodes each of which contains a reference (i.e., a link) to the next node in the sequence.

Linked lists are among the simplest and most common data structures. They can be used to implement several other common abstract data structures, including stacks, queues, associative arrays, and symbolic expressions, though it is not uncommon to implement the other data structures directly without using a list as the basis of implementation.

The principal benefit of a linked list over a conventional array is that the list elements can easily be added or removed without reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory or on disk. Linked lists allow insertion and removal of nodes at any point in the list, and can do so with a constant number of operations if the link previous to the link being added or removed is maintained during list traversal.On the other hand, simple linked lists by themselves do not allow random access to the data other than the

first node's data, or any form of efficient indexing

A list is a dynamic data structure. The number of nodes on a list may vary dramatically and dynamically as

elements are inserted and removed. For example, let us consider a list with elements 5, 3 and 8 and we need

to add an integer 6 to the front of that list. Then,

p=getnode();

info(p)=6;

next(p)=list;

list=p;

Similarly, for removing an element from the list, the process is almost exactly opposite of the process to add

a node to the front of the list. Remove the first node of a nonempty list and store the value of info field

into a variable x. then,

p=list;

list=next(p);

x=info(p);

**4.2 Representing Chains in C**

A chain is a linked list in which each node represents one element.

x There is a link or pointer from one element to the next.

x The last node has a NULL (or 0) pointer

An array and a sequential mapping is used to represent simple data structures in the previous chapters

�This representation has the property that successive nodes of the data object are stored a fixed

distance apart

(1) If the element aijis stored at location Lij, then aij+1is at the location Lij+1

(2) If the i-thelement in a queue is at location Li, then the (i+1)-th element is at location Li+1% n for the

circular representation

(3) If the topmost node of a stack is at location LT , then the node beneath it is at location LT-1, and so on

�When a sequential mapping is used for ordered lists, operations such as insertion and deletion of

arbitrary elements become expensive.

In a linked representation�To access list elements in the correct order, with each element we store the

address or location of the next element in the list�A linked list is comprised of nodes; each node has zero or

more data fields and one or more link or pointer fields.

**4.3 Linked Stacks and Queues**

**Pushing a Linked Stack**

Error code Stack :: push(const Stack entry &item)

/* Post: Stack entry item is added to the top of the Stack; returns success or

returns a code of over_ow if dynamic memory is exhausted. */

{

Node *new top = new Node(item, top node);

if (new top == NULL) return over_ow;

top node = new top;

return success;

}

**Popping a Linked Stack**

Error code Stack :: pop( )

/* Post: The top of the Stack is removed. If the Stack is empty the method returns

under_ow; otherwise it returns success. */

{

Node *old top = top node;

if (top node == NULL) return under_ow;

top node = old top->next;

delete old top;

return success;

}

A queue is a particular kind of collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position and removal of entities from the front terminal position. This makes the queue a First-In-First-Out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that once an element is added, all elements that were added before have to be removed before the new element can be invoked. A queue is an example of a linear data structure. Queues provide services, transport, and operations research where various entities such as data, objects,persons, or events are stored and held to be processed later. In these contexts, the queue performs the

function of a buffer.

#include

#include structnode{ intvalue; structnode*next;

};

voidInit(structnode*n){

n->next=NULL;

} voidEnqueue (structnode*root,intvalue){ structnode*j=(structnode*)malloc(sizeof(structnode)); j-

>value=value;

j->next=NULL;

structnode*temp ;

temp=root;

while(temp->next!=NULL)

{

temp=temp->next;

}

temp->next=j;

printf(―Value Enqueued is : %d\n‖,value);

}

voidDequeue(structnode*root)

{

if(root->next==NULL)

{

printf(―NoElementtoDequeue\n‖);

}

else

{ structnode*temp; temp=root->next;

root->next=temp->next; printf(―ValueDequeuedis%d\n‖,temp->value); free(temp);

}

}

voidmain()

{

structnodesample_queue;

Init(&sample_queue);

Enqueue(&sample_queue,10);

Enqueue(&sample_queue,50);

Enqueue(&sample_queue,570);

Enqueue(&sample_queue,5710);

Dequeue(&sample_queue);

Dequeue(&sample_queue);

Dequeue(&sample_queue);

}

**4.4 Polynomials**

A polynomial (from Greek poly, "many" and medieval Latin binomium, "binomial") is an expression of finite length constructed from variables (also known as indeterminates) and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents. For example, x2 − 4x + 7 is a polynomial, but x2 − 4/x + 7x3/2 is not, because its second term involves division by the variable x (4/x) and

because its third term contains an exponent that is not a whole number (3/2). The term "polynomial" can also be used as an adjective, for quantities that can be expressed as a polynomial of some parameter, as in "polynomial time" which is used in computational complexity theory. Polynomials appear in a wide variety of areas of mathematics and science. For example, they are used to form polynomial equations, which encode a wide range of problems, from elementary word problems to complicated problems in the sciences. A polynomial is a mathematical expression involving a sum of powers in one or more variables multiplied by coefficients.

**4.5 Additional List operations**

It is often necessary and desirable to build a variety of routines for manipulating singly linked lists. Some that we have already seen are: 1) INIT which originally links together the AV list; 2) GETNODE and 3) RETwhich get and return nodes to AV. Another useful operation is one which inverts a chain. This routine is

especially interesting because it can be done "in place" if we make use of 3 pointers.

//a chain pointed at by X is inverted so that if X = (a1, ...,am)

then after execution X = (am, ...,a1)//

p X;q 0

while p 0 do

r q;q p //r follows q; q follows p//

p LINK(p) //p moves to next node//

LINK(q) r //link q to previous node//

end

X q

end INVERT

The reader should try this algorithm out on at least 3 examples: the empty list, and lists of length 1 and 2 to

convince himself that he understands the mechanism. For a list of m 1 nodes, the while loop is executed m

times and so the computing time is linear or O(m).

Another useful subroutine is one which concatenates two chains X and Y.

procedure CONCATENATE(X, Y, Z)

//X = (a1, ...,am), Y = (b1, ...,bn), m,n 0, produces a new chain

Z = (a1, ...,am,b1 , ...,bn)//

Z X

if X = 0 then [Z Y; return]

if Y = 0 then return

p X

while LINK(p) 0 do //find last node of X//

p LINK(p)

end

LINK(p) Y //link last node of X to Y//

end CONCATENATE

This algorithm is also linear in the length of the first list. From an aesthetic point of view it is nicer to write

this procedure using the case statement in SPARKS. This would look like:

procedure CONCATENATE(X, Y, Z)

case

: X = 0 :Z Y

: Y = 0 : Z X

: else : p X; Z X

while LINK(p) 0 do

p LINK (p)

end

LINK(p) Y

end

end CONCATENATE

Suppose we want to insert a new node at the front of this list. We have to change the LINK field of the node

containing x3. This requires that we move down the entire length of A until we find the last node. It is more

convenient if the name of a circular list points to the last node rather than the first.

Now we can write procedures which insert a node at the front or at the rear of a circular list and take a fixed

amount of time.

procedure INSERT__FRONT(A, X)

//insert the node pointed at by X to the front of the circular list

A, where A points to the last node//

if A = 0 then [A X

LINK (X) A]

else [LINK(X) LINK (A)

LINK(A) X]

end INSERT--FRONT

To insert X at the rear, one only needs to add the additional statement A X to the else clause of INSERT_-

_FRONT.

As a last example of a simple procedure for circular lists, we write a function which determines the length of

such a list.

procedure LENGTH(A)

//find the length of the circular list A//

i 0

if A 0 then [ptr A

repeat

i i + 1; ptr LINK(ptr)

until ptr = A ]

return (i)

end LENGTH

**4.6 Sparse Matrices**

A sparse matrix is a matrix populated primarily with zeros (Stoer & Bulirsch 2002, p. 619). The term itself was coined by Harry M. Markowitz. Conceptually, sparsity corresponds to systems which are loosely coupled. Consider a line of balls connected by springs from one to the next; this is a sparse system. By contrast, if the same line of balls had springs

connecting each ball to all other balls, the system would be represented by a dense matrix. The concept of sparsity is useful in combinatorics and application areas such as network theory, which have a low density of significant data or connections.

A sparse matrix is a matrix that allows special techniques to take advantage of the large number of zero elements. This definition helps to define "how many" zeros a matrix needs in order to be "sparse." The answer is that it depends on what the structure of the matrix is, and what you want to do with it. For example, a randomly generated sparse matrix with entries scattered randomly throughout the matrix is not sparse in the sense of Wilkinson (for direct methods) since it takes .

**Creating a sparse matrix**

If a matrix A is stored in ordinary (dense) format, then the command S = sparse(A) creates a copy of the

matrix stored in sparse format. For example:

>> A = [0 0 1;1 0 2;0 -3 0]

A =0 0 1

1 0 2

0 -3 0

>> S = sparse(A)

S =

(2,1) 1

(3,2) -3

(1,3) 1

(2,3) 2

>> whos

Name Size Bytes Class

A 3x3 72 double array

S 3x3 64 sparse array

Grand total is 13 elements using 136 bytes

Unfortunately, this form of the sparse command is not particularly useful, since if A is large, it can be very

time-consuming to first create it in dense format. The command S = sparse(m,n) creates an zero matrix in

sparse format. Entries can then be added one-by-one:

>> A = sparse(3,2)

A =

All zero sparse: 3-by-2

>> A(1,2)=1;

>> A(3,1)=4;

>> A(3,2)=-1;

>> A

A =

(3,1) 4

(1,2) 1

(3,2) -1

**4.7 Doubly Linked Lists**

Although a circularly linked list has advantages over linear lists, it still has some drawbacks. One cannot traverse such a list backward. Double-linked lists require more space per node , and their elementary operations are more expensive; but they are often easier to manipulate because they allow sequential access to the list in both directions. In particular, one can insert or delete a node in a constant number of operations given only that node's address. (Compared with singly-linked lists, which require the previous node's address in order to correctly insert or delete.) Some algorithms require access in both directions. On the other hand, they do not allow tail-sharing, and cannot be used as persistent data structures. Operations on Doubly Linked Lists One operation that can be performed on doubly linked list but not on ordinary linked list is to delete a given

node. The following c routine deletes the node pointed by pfrom a doubly linked list and stores its contents in x. It is called by delete( p).

delete( p )

{

NODEPTR p, q, r;

int *px;

if ( p = = NULL )

{

printf(― Void Deletion \n‖);

return;

}

*px = p -> info;

q = p -> left;

r = p -> right;

q -> right = r;

r -> left = q;

freenode( p );

return;

}

A node can be inserted on the right or on the left of a given node. Let us consider insertion at right side of a

given node. The routine insert right inserts a node with information field x to right of node(p) in a doubly

linked list.

insertright( p, x) {

NODEPTR p, q, r;

int x;

if ( p = = NULL ) {

printf(― Void Insertion \n‖);

return;

}

q = getnode();

q -> info = x;

r = p -> right;

r -> left = q;

q -> right = r;

q -> left = p;

p -> left = q;

return;

}