Programming and Data Structures

Linear Data Structure 527

return 0;

}

Explanation The rem ( ) function is used to remove the specified element from the linked list. The

element to be deleted is entered by the user and then passed to the function rem ( ). In function

rem (), the entered number is checked, its last occurrence is marked, and that node is removed. The

node is assigned to a pointer temp. The free () function releases the memory allocated. Insert this

function in the previous program.

14.23 APPLICATIONS

Just for exposing to the programmer here in this section, applications of the linked list are narrated.

The programmer can refer to other books for applications of linear data structures.

The most useful linear data structure is the linked list. This paragraph introduces you to a few

applications of linear data structure useful in computer science.

Polynomial Operation

The linked list is used for implementation of polynomial arithmetic operations. The operations on

them include addition, multiplication, and so on. To have better proficiency in processing, each

polynomial is stored in decreasing order. These arrangements of polynomials in decreasing order

allow easy operation on each term. Actually, two polynomials can be added by checking each

term.

We come across polynomial operation in a calculator called reverse Polish calculator. Normally

the numbers (operands, which we call as polynomials) are entered first before the operation on

them in this calculator. Operands are pushed on the stack before operation. During operation, the

operands are called from the stack (popped) and operation would be performed. After the result is

obtained, the same would be sent back to stack.

Linked Dictionary

The role of the compiler is to create and maintain a linked dictionary that contains names. Names

can be given by combination of several symbols. Names are arranged in a symbol table and the

compiler keeps them in order. While designing a symbol table two factors are related: access time

and memory space.

The construction and referencing of a symbol table are two important phases for preparation of

a linked dictionary. Construction means insertion of symbols with their values available and

referencing is obtaining or accessing their values from the table.

The ratio of estimated number of insertions to reference is a significant factor. In symbol tables,

access retrieve time and insertion time are very much associated. The quick symbol table can be

simply constructed if large memory space is available. Each name is stored in a unique memory

location.

The easiest way to access the symbol table is linear search methods. Using a simple linked list

the symbols are organized in a sequence. The insertion can be easily done by adding symbols at the

rear of the list. If any particular symbol is to be searched, by traversing each node the required

element can be searched.

The symbol table can also be searched using binary search. All the entries in the symbol table are

sorted in ascending order. A middle entry is spotted and its value is determined. A separate topic

is given for search techniques in this book. However, this method has some drawbacks.