4.1 Introduction to Static and Dynamic Memory Allocation

FDS

Unit 4

Linked List

Memory Allocation

Memory allocation may be a process by which pc programs and services are assigned with physical or virtual storage space. The memory allocation is completed either before or at the time of program execution.

There are two sorts of memory allocations:

Compile-time or Static Memory Allocation
Run-time or Dynamic Memory Allocation

Static Memory Allocation

Static Memory is allocated for declared variables by the compiler.

The address are often found using the address of operator and may be assigned to a pointer.

The memory is allocated during compile time.

Dynamic Memory Allocation

Memory allocation done at the time of execution(run time) is understood as dynamic memory allocation.

Functions calloc () and malloc() support allocating dynamic memory

Within the Dynamic allocation of memory space is allocated by using these functions when the worth is returned by functions and assigned to pointer variables.

Difference between Static and Dynamic Memory Allocation

S. no	Static memory allocation	Dynamic memory allocation
1	In the static memory allocation, variables get allocated permanently.	I n the Dynamic memory allocation, variables get allocated as long as your program unit gets active.
2	Static Memory Allocation is completed before program execution.	Dynamics Memory Allocation is completed during program execution.
3	It uses stack for managing the static allocation of memory.	It uses heap for managing the dynamic allocation of memory.
4	It is less efficient.	It is more efficient.
5	In Static Memory Allocation, there's no memory re-usability.	In Dynamics Memory Allocation, there's memory re-usability and memory are often freed when not required.
6	In static memory allocation, once the memory is allocated, the memory size can't change.	In dynamic memory allocation, when memory is allocated the memory size are often changed.
7	During this memory allocation scheme, we cannot reuse the unused memory. this enables reusing the memory.	The user can allocate more memory when required. Also, the user can release the memory when the user needs it.
8	In this memory allocation scheme, execution is faster than dynamic memory allocation	In this memory allocation scheme, execution is slower than static memory allocation.
9	In this memory is allocated at compile time	During this memory is allocated at run time.
10	In this allocated memory remains from start to finish of the program	During this allocated memory are often released at any time during the program.
11	Example: This static memory allocation is usually used for array	Example: This dynamic memory allocation is usually used for linked list.

4.2 Linked List: Introduction

Linear arrangement and their linked storage representation.

There are many applications where sequential allocation method is unacceptable due to following characteristics:-

Unpredictable storage requirement

Extensive manipulation of stored data

The linked allocation method of storage may result in both efficient use of memory and computer time.

A linked list may be a non-sequential collection of knowledge items.

The concept of a linked list is extremely simple, for each data item within the linked list, there's an associated pointer that might give the memory allocation of subsequent data item within the linked list.

The data items within the linked list aren't during a consecutive memory locations but they'll be anywhere in memory.

Accessing of those data items is simpler as each data item contains within itself the address of subsequent data item.

Linked List

A linked list may be a collection of objects stored during a list form.

A linked list may be a sequence of things (objects) where every item is linked to subsequent.

A linked list may be a non-primitive sort of arrangement during which each element is dynamically allocated and during which elements point to every other to define a linear relationship

Elements of linked list are called nodes where each node contains two things, data and pointer to next node.

Linked list require more memory compared to array because alongside value it stores pointer to next node.

Linked lists are among the only and commonest data structures. They will be wont to implement other data structures like stacks, queues, and symbolic expressions, etc…

Operations on linked list

Insert

Insert initially position

Insert eventually position

Insert into ordered list

Delete

Traverse list (Print list)

Copy linked list

4.3 Types of Linked Lists

1. Singly Linked List

It is basic sort of linked list.

Each node contains data and pointer to next node.

Last node’s pointer is null.

Limitation of singly linked list is we will traverse only in one direction, forward direction.

$C:\Users\Kilua Zoldyck\Pictures\3.png$

2. Circular Linked List

Circular linked list may be a singly linked list where last node points to first node within the list.

It doesn't contain null pointers like singly linked list.

We can traverse only in one direction that's forward direction.

It has the most important advantage of your time saving once we want to travel from last node to first node, it directly points to first node.

An honest example of an application where circular linked list should be used may be a timesharing problem solved by the OS.

$C:\Users\Kilua Zoldyck\Pictures\2.png$

3. Doubly Linked list

Each node of doubly linked list contains data and two tips that could point previous (LPTR) and next (RPTR) node.

Main advantage of doubly linked list is we will traverse in any direction, forward or reverse.

Other advantage of doubly linked list is we will delete a node with little trouble, since we've pointers to the previous and next nodes. A node on a singly linked list can't be removed unless wehave the pointer to its predecessor.

Drawback of doubly linked list is it requires more memory compared to singly linked list because weneed an additional pointer to point previous node.

L and R in image denote left most and right most nodes within the list.

Left link of L node and right link of R node is NULL, indicating the top of list for every direction.

$C:\Users\Kilua Zoldyck\Pictures\4.png$

4. Doubly circular link list

Circular Doubly Linked List has properties of both doubly linked list and circular linked list during which two consecutive elements are linked or connected by previous and next pointer and therefore the last node points to first node by next pointer and also the primary node points to last node by previous pointer.

$C:\Users\Kilua Zoldyck\Pictures\1.png$

Advantages of Linked List

Linked lists are dynamic data structures: that's, they will grow or shrink during execution of a program.

Efficient memory utilization: Here memory isn't pre-allocated. Memory is allocated whenever it's required. And it's de-allocated (free) when it's not needed.

Insertion and deletions are easier and efficient: Linked list provide flexibility in inserting a knowledge item at a specified position and deletion of a knowledge item from the given position.

Elements of linked list are flexible: It are often primary data type or user defined data types

Disadvantages of Linked List

Random access isn't allowed. We've to access elements sequentially ranging from the primary node.

Basically we can’t perform binary search with linked lists.

It can't be easily sorted

We must traverse 1/2 the list on the average to access any element

More complex to make than an array

Extra memory space for a pointer is required with each element of the list

1. Singly linked list

1. Insertion at start first position

Function: INSERT(X, First )

Given X may be a replacement element and FIRST may be a pointer to the primary element of a linked linear list. Typical node containsINFO and LINK fields.

AVAIL may be a pointer to the highest element of the supply stack; NEW may be a temporary pointervariable.

This function inserts a replacement node at the primary position of linked list.

This function returns address ofFIRST node.

[Underflow?]
IF AVAIL = NULL
Then Write (“Availability Stack Underflow”)
Return(FIRST)

[Obtain address of next free Node]
AVAIL←NEW

[Remove free node from Availability Stack]
LINK(AVAIL)←AVAIL

[Initialize fields of latest node and its link to the list]
X←INFO (NEW)
FIRST←LINK (NEW)

[Return address of latest node]
Return (NEW)
When INSERT is invoked it returns a pointer value to the variable FIRST
INSERT (X, FIRST)←FIRST

2. Insertion at end

Function: INSEND(X, First) (Insert at end)

Given X, a replacement element and FIRST may be a pointer to the primary element of a linked linear list. Typical node contains
INFO and LINK fields.

AVAIL may be a pointer to the highest element of the supply stack; NEW may be a temporary pointer
variable.

This function inserts a replacement node at the last position of linked list.

This function returns address of FIRSTnode.

[Underflow?]
IF AVAIL = NULL
Then Write (“Availability Stack Underflow”)
Return(FIRST)

[Obtain address of next free Node]
AVAIL←NEW

[Remove free node from Availability Stack]
LINK(AVAIL)←AVAIL

[Initialize field of latest node]
X←INFO (NEW)
NULL←LINK (NEW)

[Is the list empty?]
If FIRST = NULL
then Return (NEW)

[Initialize look for a final node]
FIRST←SAVE

[Search for end of list]
Repeat while LINK (SAVE) ≠ NULL
LINK (SAVE)←SAVE

[Set link field of last node to NEW)
NEW←LINK (SAVE)

[Return first node pointer]
Return (FIRST)
When INSERTEND is invoked it returns a pointer value to the variable FIRST
INSERTEND (X, FIRST)←FIRST

3. Insert a node into Ordered Linked List

There are many applications where it's desirable to take care of an ordered linear list.

The ordering is inincreasing or decreasing order on INFO field. Such ordering leads to more efficient processing.

The overall algorithm for inserting a node into an ordered linear list is as below.

Algorithm

Remove a node from availability stack.
Set the sector of latest node.
If the linked list is empty then return the address of latest node.
If node precedes all other nodes within the list then inserts a node at the front of the list and returns itsaddress.
Repeat step 6 while information contain of the node within the list is a smaller amount than the knowledge content of the new node.
Obtain subsequent node within the linked list.
Insert the new node within the list and address of its first node.

Function: INSORD(X, FIRST)

Given X, a replacement element and FIRST may be a pointer to the primary element of a linked linear list. Typical node contains
INFO and LINK fields.

AVAIL may be a pointer to the highest element of the supply stack; NEW & SAVE are temporarypointer variables.

This function inserts a replacement node such linked list preserves the ordering of the terms inincreasing order of their INFO field.

This function returns address of FIRST node.

[Underflow?]
IF AVAIL = NULL
Then Write (“Availability Stack Underflow”)
Return(FIRST)

[Obtain address of next free Node]
AVAIL←NEW

[Remove free node from Availability Stack]
LINK(AVAIL)←AVAIL

[Is the list is empty]
If FIRST = NULL
NULL←then LINK (NEW)
Return (NEW)

[Does the new node precede all other node within the list?]
If INFO(NEW) ≤ INFO (FIRST)
FIRST←then LINK (NEW)
Return (NEW)

[Initialize temporary pointer]
FIRST←SAVE

[Search for predecessor of latest node]
Repeat while LINK (SAVE) ≠ NULL and INFO (NEW) ≥ INFO (LINK (SAVE))
LINK (SAVE)←SAVE

[Set link field of latest node and its predecessor]
LINK (SAVE)←LINK (NEW)
NEW←LINK (SAVE)

[Return first node pointer]
Return (FIRST)
When INSERTORD is invoked it returns a pointer value to the variable FIRST
INSERTORD (X, FIRST)←FIRST

4. Deletion a node from Linked List

If a linked list is empty, then write under flow and return.

Repeat step 3 while end of the list has not been reached and therefore the node has not been found.

Obtain subsequent node in list and record its predecessor node.

If the top of the list has been reached then write node not found and return.

Delete the node from list.

Return the node into availability area.

Function: DELETE(X, FIRST)

Given X, an address of node which we would like to delete and FIRST may be a pointer to the primary element of a linked linearlist.

Typical node contains INFO and LINK fields. SAVE & PRED are temporary pointer variables.

[Is Empty list?]
If FIRST = NULL
then write (‘Underflow’)
return

[Initialize look for X]
FIRST←SAVE

[Find X]
Repeat thru step-5 while SAVE ≠ X and LINK (SAVE) ≠ NULL

[Update predecessor marker]
SAVE←PRED

[Move to next node]
LINK (SAVE)←SAVE

[End of the list]
If SAVE ≠ X
then write (‘Node not found’)
return

[Delete X]
If X = FIRST (if X is first node?)
LINK (FIRST)←then FIRST
LINK (X)←else LINK (PRED)

[Free Deleted Node]
Free (X)

Function: COPY (FIRST)

FIRSTmay be a pointer to the primary node within the linked list, this function makes a replica of the list.

The new list is to contain nodes whose information and pointer fields are denoted by FIELD and PTR,respectively.

The address of the primary node within the newly created list is to be placed in BEGIN. NEW, SAVE andPRED are points variables.

A general algorithm to repeat a linked list

If the list is empty then return null
If the supply stack is empty then write availability stack underflow and return else copy the primarynode.
Report thru step 5 while the old list has not been reached.
Obtain next node in old list and record its predecessor node.
If availability stack is empty then write availability stack underflow and return else copy the node andadd it to the rear of latest list.
Set link of the last node within the new list to null and return.

[Is Empty List?]
If FIRST = NULL
then return (NULL)

[Copy first node]
NODENEW
AVAIL←New
LINK (AVAIL)←AVAIL
INFO (FIRST)←FIELD (NEW)
NEW←BEGIN

[Initialize traversal]
FIRST←SAVE

[Move subsequent node if not at the top if list]
Repeat thru step 6 while (SAVE) ≠ NULL

[Update predecessor and save pointer]
NEW←PRED
LINK (SAVE)←SAVE

[Copy node]
If AVAIL = NULL
then write (‘Availability stack underflow’)
Return (0)
AVAIL←else NEW
LINK (AVAIL)←AVAIL
INFO (SAVE)←FIELD (NEW)
NEW←PTR (PRED)

[Set link of last node and return]
NULL←PTR (NEW)
Return (BEGIN)

2. Doubly linked list

1. Insertion in first

Function: DOUBINS (L, R, M, X)

Given a doubly link list whose left most and right most nodes addressed are given by the pointer variables L andR respectively. It's required to insert a node whose address is given by the pointer variable NEW. The left andright links of nodes are denoted by LPTR and RPTR respectively. The knowledge field of a node is denoted byvariable INFO. The name of a component of the list is NODE. The insertion is to be performed to the left of aspecific node with its address given by the pointer variable M. the knowledge to be entered within the node iscontained in X.

[Create New Empty Node]

NEW NODE

2. [Copy information field]

INFO (NEW) ← X

3. [Insert into an empty list]

If R = NULL

Then LPTR (NEW) ← RPTR (NULL) ← NULL

L ← R ← NEW

Return

4. [Is left most insertion?]

If M = L

Then LPTR (NEW)←NULL

RPTR (NEW) ← M

LPTR (M)← NEW

L ← NEW

Return

5. [Insert in middle]

LPTR (NEW)← LPTR (M)

RPTR (NEW) ← M

LPTR (M) ← NEW

RPTR (LPTR (NEW)) ← NEW

6. Return

2. Insertion in middle

Function: DOUBINS_ORD (L, R, M, X)

Given a doubly link list whose left most and right most nodes addressed are given by the pointer variables L and R respectively. It's required to insert a node whose address is given by the pointer variable NEW. The left andright links of nodes are denoted by LPTR and RPTR respectively. The knowledge field of a node is denoted byvariable INFO. The name of a component of the list is NODE. The insertion is to be performed in ascending orderof info part. The knowledge to be entered within the node is contained in X.

[Create New Empty Node]

NEW NODE

2. [ Copy information field]

INFO (NEW) ← X

3. [Insert into an empty list]

If R = NULL

Then LPTR (NEW) ← RPTR (NULL) ← NULL

L ← R ← NEW

Return

4. [Does the new node precedes all other nodes in List?]

If INFO(NEW) ≤ INFO(L)

Then RPTR (NEW) ← L

LPTR(NEW)← NULL

LPTR (L) ← NEW

L ← NEW

Return

5. [Initialize temporary Pointer]

SAVE ← L

6. [Search for predecessor of latest node]

Repeat while RPTR(SAVE) ≠ NULL and INFO(NEW) ≥ INFO(RPTR(SAVE))

SAVE ← RPTR (SAVE)

7. [Set link field of latest node and its predecessor]

RPTR (NEW) ←RPTR(SAVE)

LPTR (RPTR(SAVE))←NEW

RPTR (SAVE) ← NEW

LPTR (NEW) ← SAVE

If SAVE = R

Then RPTR(SAVE)←NEW

3. Deletion in doubly link list

Function: DOUBDEL (L, R, OLD)

Given a doubly linked list with the addresses of left most and right most nodes are given by the pointer variablesL and R respectively. it's required to delete the node whose address is contained within the variable OLD. Nodecontains left and right links with names LPTR and RPTR respectively.

[Is underflow?]

If R=NULL

Then write (‘UNDERFLOW’)

return

2. 2. [Delete node]

If L = R (single node in list)

Then L ← R ← NULL

else If OLD = L (left most node)

Then L ←RPTR(L)

LPTR (L) ← NULL

else if OLD = R (right most)

Then R←LPTR (R)

RPTR (R) ← NULL

else RPTR (LPTR (OLD)) ← RPTR (OLD)

LPTR (RPTR (OLD)) ←LPTR (OLD)

3. 3. [ FREE deleted node]

FREE (OLD)

3. Circular link list

1. Insertion at start

PROCEDURE: CIRCULAR_LINK_INSERT_FIRST (X, FIRST, LAST)

FIRST and LAST are tips that could the primary and last element of a circular linked linear list respectively whose typical node contains INFO and LINK fields. NEW may be a temporary pointer variable. This procedure inserts value X at thefirst position of Circular linked linear list.

[Create New Empty Node]

NEW ← NODE

2. [Initialize fields of latest node and its link to the list]

INFO (NEW) ←X

If FIRST = NULL

Then LINK (NEW) ←NEW

FIRST ← LAST ←NEW

else LINK (NEW) ← FIRST

LINK (LAST)←NEW

FIRST ←NEW

Return

2. Insertion at end

PROCEDURE: CIR_LINK_INSERT_END (X, FIRST, LAST)

FIRST and LAST are tips that could the primary and last element of a circular linked linear list respectively whose typicalnode contains INFO and LINK fields. NEW may be a temporary pointer variable. This procedure inserts value X at thelast position of Circular linked linear list.

[Create New Empty Node]

NEW ←NODE

2. [Initialize fields of latest node and its link to the list]

If FIRST = NULL

Then LINK (NEW) ←NEW

FIRST ←LAST ← NEW

else LINK(NEW) ← FIRST

LINK(LAST) ← NEW

LAST ← NEW

Return

3. Insertion in between

PROCEDURE: CIR_LINK_INSERT_ORDER (X, FIRST, LAST)

FIRST and LAST are tips that could the primary and last element of a circular linked linear list respectively whose typicalnode contains INFO and LINK fields. NEW may be a temporary pointer variable. This procedure inserts value X suchthat linked list preserves the ordering of the terms in increasing order of their INFO field.

[Create New Empty Node]

NEW ← NODE

2. [Copy information content into new node

INFO (NEW) ← X

3. [Is Linked List is empty?]

If FIRST = NULL

Then LINK (NEW) ← NEW

FIRST ← LAST ← NEW

Return

4. Does new node precedes all other nodes in List?]

If INFO (NEW) ≤ INFO (FIRST)

Then LINK (NEW) ← FIRST

LINK (LAST) ← NEW

FIRST ← NEW

Return

5. [Initialize Temporary Pointer]

SAVE ← FIRST

6. [Search for Predecessor of latest node]

Repeat while SAVE ≠ LAST and INFO(NEW) ≥ INFO(LINK(SAVE))

SAVE ←LINK(SAVE)

7. [Set link field of latest node and its Predecessor]

LINK(NEW) ← LINK(SAVE)

LINK(SAVE) ← NEW

If SAVE = LAST

Then LAST ← NEW

8. [Finish]

Return

4. Deletion in circular link list

PROCEDURE: CIR_LINK_DELETE (X, FIRST, LAST)

FIRST and LAST are tips that could the primary and last element of a circular linked linear list respectively whose typical node contains INFO and LINK fields. SAVE & PRED are temporary pointer variables. This procedure deletes a node whose address is given by pointer variable X.

[Is Empty List?]

If FIRST = NULL

Then write (‘Linked List is Empty’)

Return

2. [Initialize look for X]

SAVE ← FIRST

3. [Find X]

Repeat thru step 5 while SAVE ≠ X and SAVE ≠ LAST

4. [Update predecessor marker]

PRED ← SAVE

5. [Move to next node]

SAVE ← LINK (SAVE)

6. [End of Linked List]

If SAVE ≠ X

Then write(‘Node not found’)

return

7. [Delete X]

If X = FIRST

Then FIRST ← LINK (FIRST)

LINK (LAST) ← FIRST

else LINK (PRED) ← LINK(X)

If X = LAST

Then LAST ← PRED

8. [Free Deleted Node]

Free (X)

4. Doubly circular link list

Insertion in CDLL

1. Insertion at the top of list or in an empty list

Empty List (start = NULL): A node (Say N) is inserted with data = 5, so previous pointer of N points to N and next pointer of N also points to N. But now start pointer points to the primary node the list.

$C:\Users\Kilua Zoldyck\Pictures\1.png$

List initially contain some nodes, start points to first node of the List: A node(Say M) is inserted with data = 7, so previous pointer of M points to last node, next pointer of M points to first node and last node’s next pointer pointsto the present M node and first node’s previous pointer points to the present M node.

$C:\Users\Kilua Zoldyck\Pictures\2.png$

2. Insertion at the start of the list:

To insert a node at the start of the list, create a node(Say T) with data = 5, T next pointer points to first node of the list, T previous pointer points to last node the list, last node’s next pointer points to the present T node, first node’s previous pointer also points this T node and eventually don’t forget to shift ‘Start’ pointer to the present T node.

$C:\Users\Kilua Zoldyck\Pictures\3.png$

3. Insertion in between the nodes of the list: To insert a node in between the list, two data values are required one after which new node are going to be inserted and another is that the data of the new node.

$C:\Users\Kilua Zoldyck\Pictures\5.png$

3. Deletion in CDLL

Case 1: Empty List(start = NULL)

If the list is empty simply return

Case 2:Initially the list contain few nodes, start points to first node of the List.

If the list isn't empty then we define two pointers curr and prev_1 and initialize the pointer curr points to first node of the list and prev_1 = NULL.

Traverse the list using curr pointer to seek out the node to be deleted and before moving curr to next node, whenever set prev_1 = curr.

If the node is found, check if it's the sole node within the list. If yes, set start = NULL and free the node pointing by curr.

If the list has quite one node, check if it's the primary node of the list. Condition to see this is often (curr == start). If yes, then move prev_1 to the last node(prev_1 = start ->prev). After prev_1 reaches the last node, set start = start -> next and prev_1 -> next = start and begin ->prev = prev_1. Free the node pointing by curr.

If curr isn't first node, we check if it's the last node within the list. Condition to see this is often (curr -> next == start). If yes, set prev_1 -> next = start and begin ->prev = prev_1. Free the node pointing by curr.

If the node to be deleted is neither the primary node nor the last node, declare another pointer temp and initialize the pointer temp points to next of curr pointer (temp = curr->next). Now set, prev_1 -> next = temp and temp ->prev = prev_1. Free the node pointing by curr.

If the given key(Say 4) matches with first node of the list(Step 4):

$C:\Users\Kilua Zoldyck\Pictures\11.png$

If the given key(Say 8) matches with last node of the list(Step 5):

$C:\Users\Kilua Zoldyck\Pictures\12.png$

If the given key(Say 6) matches with middle node of the list(Step 6):

$C:\Users\Kilua Zoldyck\Pictures\13.png$

Advantages:

List are often traversed from both the directions i.e. from head to tail or from tail to go.

Jumping from head to tail or from tail to go is completed in constant time O(1).

CDLL are mostly used for implementation of advanced data structures like Fibonacci Heap.

Disadvantages

CDLL takes a little extra memory in each node to accommodate previous pointer.

Lots of pointers involved while implementing or doing operations on an inventory.

Pointers should be handled carefully otherwise data of the list may stray.

Applications of Circular doubly linked list

Managing songs playlist in media player applications.

Managing handcart in online shopping.

4.4 Realization of linked list using dynamic memory management

Linked lists are inherently dynamic data structures; they believe new and delete (or malloc and free) for his or her operation. Normally, dynamic memory management is provided by the C/C++ standard library, with help from the OS.

Rather than representing data contiguously next to every other within the memory, linked list employs the concept of nodes and pointers.

A node holds the info item within the particular memory block and a pointer links from one node to a different and references the memory address of subsequent and former nodes (in the case of doubly linked list)

Basic allocator functionality

1. malloc(n) –

A request for n bytes of contiguous memory.

The allocator should return a pointer to such a block, if it's one available, or a null pointer if it doesn't.

The block of memory should be marked as “in-use” within the allocators internal state. (Secure allocators might zero memory before giving it over, to make sure that existing data isn't “leaked”.)

2. free(p) –

An offer to release the memory pointed to by p.

The allocator should mark the memory employed by p as not in-use. (Error-checking allocators might fill the memory with a recognizable byte pattern in order that use-after-free errors are easy to detect.)

To malloc a block,

Search through the list for a block whose size is a minimum of as big as requested. Of these blocks, we've a choice on which one to use, determined by the allocation strategy:

First Fit: use the primary block within the list which inserts

Best Fit: use the block within the list whose size is closest to the requested size.

Use the most/least recently free-d block (LIFO, FIFO).

When a block is freed,

add it to the list. this will be wiped out several ways

Add to the front of the list. (When used with first-fit, this leads to LIFO-like behavior).

Add to the rear of the list. (FIFO

Insert it into the list in order that the list is usually ordered by address. this is often commonest , because the structure of the list mirrors the structure of the memory layout.

node* new_node(long value, node* next)

{

node* n = (node*) malloc(sizeof(node));

n->value = value;

n->next = next;

return n;

}

A list will be identified by a node*. Hence, new_node above is also a kind of push_front, adding a new node to the beginning of a list.

Inserting a value

To insert a value, we pass a pointer to the node before the location to insert at, as well as the value to be inserted. In C, we would do

node* insert(node* p, long value)

{

node* n = new_node(value, p->next);

p->next = n;

return n;

}

Removing a node

Similarly, to remove a node, we pass a pointer to the node before it.

void remove(node* p)

{

node* n = p->next;

if(p->next)

p->next = p->next->next;

free(n);

}

4.5 Linked List as ADT

Linked List as an ADT:

A linked list may be a chain of nodes where each node within the list consists of two fields, a knowledge field and a next address field.

The data field holds the particular element on the list where subsequent address field contains the address of next node within the list. Hence, subsequent address field is just a regard to subsequent node.

The entire linked list is accessed from the reference variable first that points to the primary node within the list.

The next address field of the last node within the list contains a special value referred to as null, which isn't a legitimate address. The value null is employed to signal end of the list.

The list with no nodes is named as empty list or null list. In such cases, the value of pointer first=null. Moreover, a linked list is initialized to empty list by the operation first=null.

A linked list is a dynamic data structure. The number of nodes in the list may vary as elements are inserted or removed.

Just like a stack or queue, a linked list in itself may be aarrangement. The data field of every node stores the particular information we will apply several operations on the list. Some of the most common operations include insertion of nodes, deletion of nodes, list traversal etc.

4.6 Basic primitive operations on linked list

1. Insert

Insert ion at beginning

Allocate memory for new node

Store data

Change next of new node to point to head

Change head to point to recently created node

Insertion at end

Allocate memory for new node

Store data

Traverse to last node

Change next of last node to recently created node

Insertion in middle

Allocate memory and store data for new node

Traverse to node just before the required position of new node

Change next pointers to include new node in between

2. Deletion

Delete from beginning

Point head to the second node

Deletion from end

Traverse to second last element

Change its next pointer to null

Deletion from middle

Traverse to element before the element to be deleted

Change next pointers to exclude the node from the chain

3. Traverse

Traversing is simply displaying the list of link list

We have to keep moving the temp node to the next one and display its contents.

When temp node is NULL,

We have reached the end of link list and then stop the while loop.

4. Concatenate

Suppose we have 2 link list (like p and q are 2 link list)

Traverse the 1st link list till the end then store the address of first node in 2nd list in the last node of 1st list.

$C:\Users\Kilua Zoldyck\Pictures\aaaaaa.png$

4.7 Generalized Linked List

A Generalized Linked List L, is defined as a finite sequence of n>=0 elements, l1, l2, l3, l4, …,ln, such that li are either atom or the list of atoms. Thus
L = (l1, l2, l3, l4, …,ln)
where n is total number of nodes in the list.

Flag

Data

Down pointer

Next pointer

To represent a list of items there are certain assumptions about the node structure.

Flag = 1 implies that down pointer exists

Flag = 0 implies that next pointer exists

Data means the atom

Down pointer is the address of node which is down of the current node

Next pointer is the address of node which is attached as the next node

Generalized linked lists are used because although the efficiency of polynomial operations using linked list is good but still, the disadvantage is that the linked list is unable to use multiple variable polynomial equation efficiently. It helps us to represent multi-variable polynomial along with the list of elements.

Typical ‘C’ structure of Generalized Linked List

typedefstruct node{

Char c; //data

int index; //flag

struct node*next,*down; //next and down pointer

} GLL;

Example of GLL {List representation}
( a, (b, c), d)

$C:\Users\Kilua Zoldyck\Pictures\gl1.png$
When first field is 0, it indicates that the second field is variable. If first field is 1 means the second field is a down pointer, means some list is starting.

The typical node structure will be:

Flag

Var

Exp

Next pointer

Here Flag = 0 means variable is present

Flag = 1 means down pointer is present

Flag = 2 means coefficient and exponent is present

Example:
9x5 + 7xy4 + 10xz
$C:\Users\Kilua Zoldyck\Pictures\gl2.png$

In the above example the top node is of variable x. The temp node shows the primary field as 2 means coefficient and exponent are present.

$C:\Users\Kilua Zoldyck\Pictures\gl3.png$

Since temp node is attached to go node and head node has variable x, temp node having coefficient = 9 and exponent = 5. The above two nodes are often read as 9x5.

$C:\Users\Kilua Zoldyck\Pictures\gl4.png$

Similarly, within the above figure, the node temp1 are often read as x4.

The flag field is 1 means down pointer is there

temp2 = y

temp3 = coefficient = 7

exponent = 1

flag = 2 means the node contains coefficient and exponent values.

temp2 is attached to temp3 this suggests 7y1 and temp2 is additionally attached to

temp1 means temp1 x temp2

x4 x 7y1 = 7x4y1 value is represented by above figure

4.8 Polynomial Representation using Generalized Linked List

Linked list may be an arrangement that stores each element as an object during a node of the list. Every note contains two parts data han and links to subsequent node.

Polynomial may be a mathematical expression that consists of variables and coefficients. for instance x^2 - 4x + 7

In the Polynomial linked list, the coefficients and exponents of the polynomial are defined because the data node of the list.

For adding two polynomials that are stored as a linked list. We’d like to feature the coefficients of variables with an equivalent power. During a linked list node contains 3 members, coefficient value link to subsequent node.

A linked list that's wont to store Polynomial seems like –

For all power, we'll check for the coefficients of the exponents that have an equivalent value of exponents and add them.

Then return the ultimate polynomial.

On addition on p1 and p2 we get resultant polynomial as P

Input - Polynomial P1 and P2 represented as a linked list.

Polynomial

P1= 13x8 +7x5 + 32x2 +54

P2=3x12 +17x5 + 3x3 +98

Algorithm

Step 1: loop around all values of linked list and follow step 2& 3.

Step 2: if the value of a node’s exponent. Is greater copy this node to result node and head towards the next node.

Step 3: if the values of both node’s exponent is same add the coefficients and then copy the added value with node to the result.