Linear Data Structure 527
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.
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.
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
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.
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
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.