Ø Pointer: A pointer is a variable which contains an
address of another variable in memory.It is declared by * indicator.
Ø We can create a pointer variable in C using
following syntax:
Data type *pointer name;
Ø For example:
Here, ptr is a
pointer to integer data type.
Ø the use of a pointer(link) to refer to the
element of data structure implies that, Elements
which are logically adjacent need not be physically adjacent in Memory is
known as linked allocation.
Linked
lists & Sequential list
Ø A singly linked list is to expand each node
to contain a link or pointer to the next node. This is also called as a one way
chain.
Ø For example:
Ø First contain the address of the first node
of the list.
Ø Each node in the list consist of two parts:
1. Information(INFO)
2. Address or pointer to next node(LINK)
Ø In link list each node contains a Link and INFO. INFO part contains
the actual element of list. Link or
pointer contains the address of next node in the list. Last node indicates end
of list contains a special value, known as a “NULL”. Link(Next)=NULL.
Difference between Linked list and Sequential list
Linked List
|
Sequential List
|
1. In linked list number of elements in
the list is not fixed.
|
1. in sequential list number of elements
in list is fixed.
|
2. In linked list allocation of memory is
done at runtime.
|
2. In sequential list allocation of
memory is done at compile time.
|
3. Insertion and deletion operation are
very easy and less time consuming in linked list.
|
3. Insertion and deletion operation are
very lengthy and time consuming in sequential list
|
4. In linked list we require pointer
variable which occupies extra memory space.
|
4. In sequential list there is no need to
use pointer variable so it does not occupies extra memory space.
|
5. Searching in a linked list is very
time consuming because we have to traverse entire list even if all the
elements in the list are sorted.
|
5. Searching is less time consuming in
sequential list because we can use binary search method to search an element
which is very efficient.
|
6. In linked list the elements which are
logically adjacent need not be physically adjacent.
|
6. In sequential list elements are
logically and physically adjacent to each other.
|
7. It is very easy to join or split two
lists.
|
7. It is very difficult to split or join
two lists.
|
Ø Representation of Singly linked linear list
is shown below:
Ø Here, the variable FIRST contains an address of the first node in the list.
Ø The last node of the list does not have any successor node, so it does not contain any address in its link field. In such case a NULL value is stored as an address. NULL indicates end of the list.
Operations
on Linked list
Ø Followings are the operations that can be
performed on linked list.
1. Traversing a linked list.
2. Insert new node at beginning of the list
3. Insert new node at end of the list
4. Insert new node into ordered list
5. Insert new node at any position or in between
the list.
6. Delete first node of the list
7. Delete last node of the list.
8. Delete node from any specific position in
the list.
9. Searching element in list.
10. Merging of two linked list.
11. Sorting operation of list.
12. Copy of the list.
Algorithms for Singly linked list
1. Algorithm to
insert new node at beginning of the linked list
 |
INSERTBEG (VAL,FIRST)
Ø This function inserts a new element VAL at
the beginning of the linked list.
Ø FIRST is a pointer which contains address
of first node in the list.
1.
[Check for availability stack underflow]
If AVAIL = NULL then
Write “Availability stack underflow”
Return
2.
[Obtain address of next free node]
NEWßAVAIL
3.
[Remove free node from availability stack]
AVAILßLINK
(AVAIL)
4.
[Initialize node to the linked list]
INFO (NEW) ßVAL
LINK (NEW) ßNULL
5.
[Assign the address of the Temporary node to
the First Node ]
FIRSTßNEW
6.
[Finished]
Return (FIRST)
2. Algorithm to
insert new node at end of the linked list
4. Algorithm to insert new node in ordered linked list
INSERTEND (VAL,FIRST)
Ø This function inserts a new element VAL at
the end of the linked list.
Ø FIRST is a pointer which contains address
of first node in the list.
1.
[Check for availability stack underflow]
If AVAIL = NULL then
Write “Availability stack underflow”
Return
2.
[Obtain address of next free node]
NEWßAVAIL
3.
[Remove free node from availability stack]
AVAILßLINK
(AVAIL)
4.
[initialize field of new node]
INFO (NEW) ßVAL
LINK (NEW) ßNULL
5.
[If list is empty?]
If FIRST = NULL then
FIRSTßNEW
6.
[initialize search for last node]
SAVEßFIRST
7.
[Search end of the list]
Repeat while LINK (SAVE) ≠ NULL
SAVEßLINK
(SAVE)
8.
[Set LINK field of last node to NEW ]
LINK (SAVE) ßNEW
9. [Finished]
3. Algorithm to insert new node at specific
location
INSPOS (VAL, FIRST, N)
Ø This function inserts a new element VAL
into the linked list specified by address N.
Ø FIRST is a pointer which contains address
of first node in the list.
1. [Check for availability stack underflow]
If AVAIL = NULL then
Write “Availability stack
underflow”
Return
2. [Obtain address of next free node]
NEWßAVAIL
3. [Remove free node from availability stack]
AVAILßLINK (AVAIL)
4. [initialize field of new node]
INFO (NEW) ßVAL
5. [If list is empty?]
If FIRST = NULL then
LINK (NEW) ßNULL
FIRSTßNEW
6. [Search the list until desired address
found]
SAVEßFIRST
Repeat while LINK (SAVE) ≠ NULL
and SAVE ≠ N
PREDßSAVE
SAVEßLINK (SAVE)
7. [Node found]
LINK (PRED) ßNEW
8. [Finished]
Return (FIRST)
4. Algorithm to insert new node in ordered linked list
DELFIRST(FIRST)
Ø
This function deletes a first node from the
list.
Ø
FIRST is a pointer which contains address of
first node in the list.
1.
[Check for empty list]
If
(FIRST = NULL) then
Write “List is empty”
Return
2.
[Check for the element in the list and
delete it]
If LINK (FIRST) = NULL then
YßINFO
(FIRST)
FIRSTßNULL
Else
TEMPßFIRST
YßINFO
(TEMP)
FIRSTßLINK (TEMP)
3.
[Finished]
Return (FIRST)
6. Algorithm to
delete last node of linked list
DELLAST(FIRST)
Ø
This function deletes a last node from the
list.
Ø
FIRST is a pointer which contains address of
first node in the list
1.[Check for empty list]
If FIRST
= NULL then
Write
“List is empty”
Return
2.
[Check for the element in the list and
delete it]
If LINK
(FIRST) = NULL then
YßINFO
(FIRST)
FIRSTßNULL
Else
(Assign
the address pointed by FIRST pointer to TEMP pointer)
TEMPßFIRST
Repeat
while LINK (TEMP) ≠ NULL
PREDßTEMP
TEMPßLINK
(TEMP)
3.
[Delete Last Node]
YßINFO
(TEMP)
LINK
(PRED) ßNULL
4.
[Finished]
Return
(FIRST)
7. Algorithm to delete specific node from linked
list
DELPOS(FIRST,N)
Ø This function deletes a node from specific
location from the list.
Ø FIRST is a pointer which contains address
of first node in the list.
1.
[Check for empty list]
If FIRST = NULL then
Write “List is empty”
Return
2.
[If there is only one node?]
If LINK
(FIRST) = NULL then
YßINFO (FIRST)
FIRSTßNULL
3.
[If
list contains more than one node?]
TEMPßFIRST
Repeat while LINK (TEMP) ≠ NULL and TEMP ≠ N
PREDßTEMP
TEMPßLINK
(TEMP)
4.
[Node found?]
If TEMP ≠ N then
Write “Node not found”
Else
YßINFO (TEMP)
LINK (PRED) ßLINK (TEMP)
5.
[Finished]
Return (FIRST)
0 Comments