C++ PROGRAMMING & DATA STRUCTURES

20BHM202
UNIT 4

BY
SYED JAMALULLAH R
DEFINITION OF A DATA STRUCTURE:
IN COMPUTER PROGRAMMING, A DATA STRUCTURE MAY BE SELECTED OR DESIGNED TO STORE DATA FOR THE
PURPOSE OF WORKING ON IT WITH VARIOUS ALGORITHMS. EACH DATA STRUCTURE CONTAINS INFORMATION ABOUT
THE DATA VALUES, RELATIONSHIPS BETWEEN THE DATA AND FUNCTIONS THAT CAN BE APPLIED TO THE DATA.

THE DATA STRUCTURE NAME INDICATES ITSELF THAT ORGANIZING THE DATA IN MEMORY. THERE ARE MANY WAYS
OF ORGANIZING THE DATA IN THE MEMORY AS WE HAVE ALREADY SEEN ONE OF THE DATA STRUCTURES, I.E., ARRAY
IN C LANGUAGE. ARRAY IS A COLLECTION OF MEMORY ELEMENTS IN WHICH DATA IS STORED SEQUENTIALLY, I.E.,
ONE AFTER ANOTHER. IN OTHER WORDS, WE CAN SAY THAT ARRAY STORES THE ELEMENTS IN A CONTINUOUS
MANNER. THIS ORGANIZATION OF DATA IS DONE WITH THE HELP OF AN ARRAY OF DATA STRUCTURES. THERE ARE
ALSO OTHER WAYS TO ORGANIZE THE DATA IN MEMORY. LET'S SEE THE DIFFERENT TYPES OF DATA STRUCTURES.

THE DATA STRUCTURE IS NOT ANY PROGRAMMING LANGUAGE LIKE C, C++, JAVA, ETC. IT IS A SET OF ALGORITHMS
THAT WE CAN USE IN ANY PROGRAMMING LANGUAGE TO STRUCTURE THE DATA IN THE MEMORY.

TO STRUCTURE THE DATA IN MEMORY, 'N' NUMBER OF ALGORITHMS WERE PROPOSED, AND ALL THESE ALGORITHMS
ARE KNOWN AS ABSTRACT DATA TYPES. THESE ABSTRACT DATA TYPES ARE THE SET OF RULES.
TYPES OF DATA STRUCTURES
THERE ARE TWO TYPES OF DATA STRUCTURES:
• PRIMITIVE DATA STRUCTURE
• NON-PRIMITIVE DATA STRUCTURE
PRIMITIVE DATA STRUCTURE
THE PRIMITIVE DATA STRUCTURES ARE PRIMITIVE DATA TYPES. THE INT, CHAR, FLOAT, DOUBLE,
AND POINTER ARE THE PRIMITIVE DATA STRUCTURES THAT CAN HOLD A SINGLE VALUE.
NON-PRIMITIVE DATA STRUCTURE
THE NON-PRIMITIVE DATA STRUCTURE IS DIVIDED INTO TWO TYPES:
• LINEAR DATA STRUCTURE
• NON-LINEAR DATA STRUCTURE
LINEAR DATA STRUCTURE:
THE ARRANGEMENT OF DATA IN A SEQUENTIAL MANNER IS KNOWN AS A LINEAR DATA
STRUCTURE. THE DATA STRUCTURES USED FOR THIS PURPOSE ARE ARRAYS, LINKED LIST,
STACKS, AND QUEUES. IN THESE DATA STRUCTURES, ONE ELEMENT IS CONNECTED TO ONLY
ONE ANOTHER ELEMENT IN A LINEAR FORM.
WHEN ONE ELEMENT IS CONNECTED TO THE 'N' NUMBER OF ELEMENTS KNOWN AS A NON-
LINEAR DATA STRUCTURE. THE BEST EXAMPLE IS TREES AND GRAPHS. IN THIS CASE, THE
ELEMENTS ARE ARRANGED IN A RANDOM MANNER.
WE WILL DISCUSS THE ABOVE DATA STRUCTURES IN BRIEF IN THE COMING TOPICS. NOW, WE
WILL SEE THE COMMON OPERATIONS THAT WE CAN PERFORM ON THESE DATA STRUCTURES.
DATA STRUCTURES CAN ALSO BE CLASSIFIED AS:
STATIC DATA STRUCTURE: IT IS A TYPE OF DATA STRUCTURE WHERE THE SIZE IS
ALLOCATED AT THE COMPILE TIME. THEREFORE, THE MAXIMUM SIZE IS FIXED.
DYNAMIC DATA STRUCTURE: IT IS A TYPE OF DATA STRUCTURE WHERE THE SIZE IS
ALLOCATED AT THE RUN TIME. THEREFORE, THE MAXIMUM SIZE IS FLEXIBLE.
MAJOR OPERATIONS
THE MAJOR OR THE COMMON OPERATIONS THAT CAN BE PERFORMED ON THE DATA
STRUCTURES ARE:
SEARCHING: WE CAN SEARCH FOR ANY ELEMENT IN A DATA STRUCTURE.
SORTING: WE CAN SORT THE ELEMENTS OF A DATA STRUCTURE EITHER IN AN
ASCENDING OR DESCENDING ORDER.
INSERTION: WE CAN ALSO INSERT THE NEW ELEMENT IN A DATA STRUCTURE.
UPDATION: WE CAN ALSO UPDATE THE ELEMENT, I.E., WE CAN REPLACE THE ELEMENT
WITH ANOTHER ELEMENT.
DELETION: WE CAN ALSO PERFORM THE DELETE OPERATION TO REMOVE THE ELEMENT
FROM THE DATA STRUCTURE.
WHICH DATA STRUCTURE?
A DATA STRUCTURE IS A WAY OF ORGANIZING THE DATA SO THAT IT CAN BE USED
EFFICIENTLY. HERE, WE HAVE USED THE WORD EFFICIENTLY, WHICH IN TERMS OF BOTH
THE SPACE AND TIME. FOR EXAMPLE, A STACK IS AN ADT (ABSTRACT DATA TYPE) WHICH
USES EITHER ARRAYS OR LINKED LIST DATA STRUCTURE FOR THE IMPLEMENTATION.
THEREFORE, WE CONCLUDE THAT WE REQUIRE SOME DATA STRUCTURE TO IMPLEMENT A
PARTICULAR ADT.
AN ADT TELLS WHAT IS TO BE DONE AND DATA STRUCTURE TELLS HOW IT IS TO BE
DONE. IN OTHER WORDS, WE CAN SAY THAT ADT GIVES US THE BLUEPRINT WHILE DATA
STRUCTURE PROVIDES THE IMPLEMENTATION PART. NOW THE QUESTION ARISES: HOW
CAN ONE GET TO KNOW WHICH DATA STRUCTURE TO BE USED FOR A PARTICULAR ADT?.
AS THE DIFFERENT DATA STRUCTURES CAN BE IMPLEMENTED IN A PARTICULAR ADT, BUT
THE DIFFERENT IMPLEMENTATIONS ARE COMPARED FOR TIME AND SPACE. FOR
EXAMPLE, THE STACK ADT CAN BE IMPLEMENTED BY BOTH ARRAYS AND LINKED LIST.
SUPPOSE THE ARRAY IS PROVIDING TIME EFFICIENCY WHILE THE LINKED LIST IS
PROVIDING SPACE EFFICIENCY, SO THE ONE WHICH IS THE BEST SUITED FOR THE
CURRENT USER'S REQUIREMENTS WILL BE SELECTED.
ADVANTAGES OF DATA STRUCTURES
THE FOLLOWING ARE THE ADVANTAGES OF A DATA STRUCTURE:

EFFICIENCY: IF THE CHOICE OF A DATA STRUCTURE FOR IMPLEMENTING A PARTICULAR

ADT IS PROPER, IT MAKES THE PROGRAM VERY EFFICIENT IN TERMS OF TIME AND SPACE.

REUSABILITY: THE DATA STRUCTURE PROVIDES REUSABILITY MEANS THAT MULTIPLE

CLIENT PROGRAMS CAN USE THE DATA STRUCTURE.

ABSTRACTION: THE DATA STRUCTURE SPECIFIED BY AN ADT ALSO PROVIDES THE LEVEL
OF ABSTRACTION. THE CLIENT CANNOT SEE THE INTERNAL WORKING OF THE DATA
STRUCTURE, SO IT DOES NOT HAVE TO WORRY ABOUT THE IMPLEMENTATION PART. THE
CLIENT CAN ONLY SEE THE INTERFACE.
STACK:
A STACK IS AN ABSTRACT DATA TYPE (ADT), COMMONLY USED IN MOST PROGRAMMING
LANGUAGES. IT IS NAMED STACK AS IT BEHAVES LIKE A REAL-WORLD STACK, FOR EXAMPLE
– A DECK OF CARDS OR A PILE OF PLATES, ETC.

A REAL-WORLD STACK ALLOWS OPERATIONS AT ONE END ONLY. FOR EXAMPLE, WE CAN
PLACE OR REMOVE A CARD OR PLATE FROM THE TOP OF THE STACK ONLY. LIKEWISE, STACK
ADT ALLOWS ALL DATA OPERATIONS AT ONE END ONLY. AT ANY GIVEN TIME, WE CAN ONLY
ACCESS THE TOP ELEMENT OF A STACK.
THIS FEATURE MAKES IT LIFO DATA STRUCTURE. LIFO STANDS FOR LAST-IN-FIRST-OUT. HERE,
THE ELEMENT WHICH IS PLACED (INSERTED OR ADDED) LAST, IS ACCESSED FIRST. IN STACK
TERMINOLOGY, INSERTION OPERATION IS CALLED PUSH OPERATION AND REMOVAL
OPERATION IS CALLED POP OPERATION.
STACK REPRESENTATION
THE FOLLOWING DIAGRAM DEPICTS A STACK AND ITS OPERATIONS −

A STACK CAN BE IMPLEMENTED BY MEANS OF ARRAY, STRUCTURE, POINTER, AND

LINKED LIST. STACK CAN EITHER BE A FIXED SIZE ONE OR IT MAY HAVE A SENSE OF
DYNAMIC RESIZING. HERE, WE ARE GOING TO IMPLEMENT STACK USING ARRAYS, WHICH
MAKES IT A FIXED SIZE STACK IMPLEMENTATION.
BASIC OPERATIONS
STACK OPERATIONS MAY INVOLVE INITIALIZING THE STACK, USING IT AND THEN DE-
INITIALIZING IT. APART FROM THESE BASIC STUFFS, A STACK IS USED FOR THE
FOLLOWING TWO PRIMARY OPERATIONS −
PUSH() − PUSHING (STORING) AN ELEMENT ON THE STACK.
POP() − REMOVING (ACCESSING) AN ELEMENT FROM THE STACK.
WHEN DATA IS PUSHED ONTO STACK.
TO USE A STACK EFFICIENTLY, WE NEED TO CHECK THE STATUS OF STACK AS WELL. FOR
THE SAME PURPOSE, THE FOLLOWING FUNCTIONALITY IS ADDED TO STACKS −
PEEK() − GET THE TOP DATA ELEMENT OF THE STACK, WITHOUT REMOVING IT.
ISFULL() − CHECK IF STACK IS FULL.
ISEMPTY() − CHECK IF STACK IS EMPTY.
AT ALL TIMES, WE MAINTAIN A POINTER TO THE LAST PUSHED DATA ON THE STACK. AS
THIS POINTER ALWAYS REPRESENTS THE TOP OF THE STACK, HENCE NAMED TOP.
THE TOP POINTER PROVIDES TOP VALUE OF THE STACK WITHOUT ACTUALLY REMOVING
IT.
PUSH OPERATION
THE PROCESS OF PUTTING A NEW DATA ELEMENT ONTO STACK IS KNOWN AS A PUSH
OPERATION. PUSH OPERATION INVOLVES A SERIES OF STEPS −
STEP 1 − CHECKS IF THE STACK IS FULL.
STEP 2 − IF THE STACK IS FULL, PRODUCES AN ERROR AND EXIT.
STEP 3 − IF THE STACK IS NOT FULL, INCREMENTS TOP TO POINT NEXT EMPTY SPACE.
STEP 4 − ADDS DATA ELEMENT TO THE STACK LOCATION, WHERE TOP IS POINTING.
STEP 5 − RETURNS SUCCESS.

IF THE LINKED LIST IS USED TO IMPLEMENT THE STACK, THEN IN STEP 3, WE NEED TO
ALLOCATE SPACE DYNAMICALLY.
POP OPERATION
ACCESSING THE CONTENT WHILE REMOVING IT FROM THE STACK, IS KNOWN AS A POP
OPERATION. IN AN ARRAY IMPLEMENTATION OF POP() OPERATION, THE DATA ELEMENT IS
NOT ACTUALLY REMOVED, INSTEAD TOP IS DECREMENTED TO A LOWER POSITION IN THE
STACK TO POINT TO THE NEXT VALUE. BUT IN LINKED-LIST IMPLEMENTATION, POP()
ACTUALLY REMOVES DATA ELEMENT AND DEALLOCATES MEMORY SPACE.
A POP OPERATION MAY INVOLVE THE FOLLOWING STEPS −
STEP 1 − CHECKS IF THE STACK IS EMPTY.
STEP 2 − IF THE STACK IS EMPTY, PRODUCES AN ERROR AND EXIT.
STEP 3 − IF THE STACK IS NOT EMPTY, ACCESSES THE DATA ELEMENT AT WHICH TOP IS
POINTING.
STEP 4 − DECREASES THE VALUE OF TOP BY 1.
STEP 5 − RETURNS SUCCESS.
IMPLEMENT A STACK USING SINGLY LINKED LIST
IMPLEMENT A STACK USING SINGLE LINKED LIST CONCEPT. ALL THE SINGLE LINKED
LIST OPERATIONS PERFORM BASED ON STACK OPERATIONS LIFO(LAST IN FIRST OUT) AND
WITH THE HELP OF THAT KNOWLEDGE WE ARE GOING TO IMPLEMENT A STACK USING
SINGLE LINKED LIST. USING SINGLE LINKED LISTS SO HOW TO IMPLEMENT HERE IT IS
LINKED LIST MEANS WHAT WE ARE STORING THE INFORMATION IN THE FORM OF NODES
AND WE NEED TO FOLLOW THE STACK RULES AND WE NEED TO IMPLEMENT USING
SINGLE LINKED LIST NODES SO WHAT ARE THE RULES WE NEED TO FOLLOW IN THE
IMPLEMENTATION OF A STACK A SIMPLE RULE THAT IS LAST IN FIRST OUT AND ALL THE
OPERATIONS WE SHOULD PERFORM SO WITH THE HELP OF A TOP VARIABLE ONLY WITH
THE HELP OF TOP VARIABLES ARE HOW TO INSERT THE ELEMENTS LET’S SEE
A STACK CAN BE EASILY IMPLEMENTED THROUGH THE LINKED LIST. IN STACK
IMPLEMENTATION, A STACK CONTAINS A TOP POINTER. WHICH IS “HEAD” OF THE STACK
WHERE PUSHING AND POPPING ITEMS HAPPENS AT THE HEAD OF THE LIST. FIRST NODE
HAVE NULL IN LINK FIELD AND SECOND NODE LINK HAVE FIRST NODE ADDRESS IN LINK
FIELD AND SO ON AND LAST NODE ADDRESS IN “TOP” POINTER.
THE MAIN ADVANTAGE OF USING LINKED LIST OVER AN ARRAYS IS THAT IT IS POSSIBLE
TO IMPLEMENTS A STACK THAT CAN SHRINK OR GROW AS MUCH AS NEEDED. IN USING
ARRAY WILL PUT A RESTRICTION TO THE MAXIMUM CAPACITY OF THE ARRAY WHICH
CAN LEAD TO STACK OVERFLOW. HERE EACH NEW NODE WILL BE DYNAMICALLY
ALLOCATE. SO OVERFLOW IS NOT POSSIBLE.

STACK OPERATIONS:
PUSH() : INSERT THE ELEMENT INTO LINKED LIST NOTHING BUT WHICH IS THE TOP NODE
OF STACK.
POP() : RETURN TOP ELEMENT FROM THE STACK AND MOVE THE TOP POINTER TO THE
SECOND NODE OF LINKED LIST OR STACK.
PEEK(): RETURN THE TOP ELEMENT.
APPLICATIONS OF STACK IN DATA STRUCTURE:
THE STACK IS LAST IN FIRST OUT (LIFO) DATA STRUCTURE. THIS DATA STRUCTURE HAS SOME IMPORTANT APPLICATIONS IN
DIFFERENT ASPECT. THESE ARE LIKE BELOW −
EXPRESSION HANDLING −
INFIX TO POSTFIX OR INFIX TO PREFIX CONVERSION −
THE STACK CAN BE USED TO CONVERT SOME INFIX EXPRESSION INTO ITS POSTFIX EQUIVALENT, OR PREFIX EQUIVALENT. THESE POSTFIX OR
PREFIX NOTATIONS ARE USED IN COMPUTERS TO EXPRESS SOME EXPRESSIONS. THESE EXPRESSIONS ARE NOT SO MUCH FAMILIAR TO THE
INFIX EXPRESSION, BUT THEY HAVE SOME GREAT ADVANTAGES ALSO. WE DO NOT NEED TO MAINTAIN OPERATOR ORDERING, AND
PARENTHESIS.
POSTFIX OR PREFIX EVALUATION −
AFTER CONVERTING INTO PREFIX OR POSTFIX NOTATIONS, WE HAVE TO EVALUATE THE EXPRESSION TO GET THE RESULT. FOR THAT PURPOSE,
ALSO WE NEED THE HELP OF STACK DATA STRUCTURE.

BACKTRACKING PROCEDURE −
BACKTRACKING IS ONE OF THE ALGORITHM DESIGNING TECHNIQUE. FOR THAT PURPOSE, WE DIVE INTO SOME WAY, IF THAT
WAY IS NOT EFFICIENT, WE COME BACK TO THE PREVIOUS STATE AND GO INTO SOME OTHER PATHS. TO GET BACK FROM
CURRENT STATE, WE NEED TO STORE THE PREVIOUS STATE. FOR THAT PURPOSE, WE NEED STACK. SOME EXAMPLES OF
BACKTRACKING IS FINDING THE SOLUTION FOR KNIGHT TOUR PROBLEM OR N-QUEEN PROBLEM ETC.
ANOTHER GREAT USE OF STACK IS DURING THE FUNCTION CALL AND RETURN PROCESS. WHEN WE CALL A FUNCTION FROM
ONE OTHER FUNCTION, THAT FUNCTION CALL STATEMENT MAY NOT BE THE FIRST STATEMENT. AFTER CALLING THE
FUNCTION, WE ALSO HAVE TO COME BACK FROM THE FUNCTION AREA TO THE PLACE, WHERE WE HAVE LEFT OUR CONTROL.
SO WE WANT TO RESUME OUR TASK, NOT RESTART. FOR THAT REASON, WE STORE THE ADDRESS OF THE PROGRAM COUNTER
INTO THE STACK, THEN GO TO THE FUNCTION BODY TO EXECUTE IT. AFTER COMPLETION OF THE EXECUTION, IT POPS OUT
THE ADDRESS FROM STACK AND ASSIGN IT INTO THE PROGRAM COUNTER TO RESUME THE TASK AGAIN.
QUEUE:
QUEUE IS AN ABSTRACT DATA STRUCTURE, SOMEWHAT SIMILAR TO STACKS. UNLIKE
STACKS, A QUEUE IS OPEN AT BOTH ITS ENDS. ONE END IS ALWAYS USED TO INSERT DATA
(ENQUEUE) AND THE OTHER IS USED TO REMOVE DATA (DEQUEUE). QUEUE FOLLOWS
FIRST-IN-FIRST-OUT METHODOLOGY, I.E., THE DATA ITEM STORED FIRST WILL BE
ACCESSED FIRST.

A REAL-WORLD EXAMPLE OF QUEUE CAN BE A SINGLE-LANE ONE-WAY ROAD, WHERE

THE VEHICLE ENTERS FIRST, EXITS FIRST. MORE REAL-WORLD EXAMPLES CAN BE SEEN
AS QUEUES AT THE TICKET WINDOWS AND BUS-STOPS.
QUEUE REPRESENTATION
AS WE NOW UNDERSTAND THAT IN QUEUE, WE ACCESS BOTH ENDS FOR DIFFERENT
REASONS. THE FOLLOWING DIAGRAM GIVEN BELOW TRIES TO EXPLAIN QUEUE
REPRESENTATION AS DATA STRUCTURE −

AS IN STACKS, A QUEUE CAN ALSO BE IMPLEMENTED USING ARRAYS, LINKED-LISTS,

POINTERS AND STRUCTURES. FOR THE SAKE OF SIMPLICITY, WE SHALL IMPLEMENT
QUEUES USING ONE-DIMENSIONAL ARRAY.
BASIC OPERATIONS
QUEUE OPERATIONS MAY INVOLVE INITIALIZING OR DEFINING THE QUEUE, UTILIZING IT,
AND THEN COMPLETELY ERASING IT FROM THE MEMORY. HERE WE SHALL TRY TO
UNDERSTAND THE BASIC OPERATIONS ASSOCIATED WITH QUEUES −
ENQUEUE() − ADD (STORE) AN ITEM TO THE QUEUE.
DEQUEUE() − REMOVE (ACCESS) AN ITEM FROM THE QUEUE.
FEW MORE FUNCTIONS ARE REQUIRED TO MAKE THE ABOVE-MENTIONED QUEUE
OPERATION EFFICIENT. THESE ARE −
PEEK() − GETS THE ELEMENT AT THE FRONT OF THE QUEUE WITHOUT REMOVING IT.
ISFULL() − CHECKS IF THE QUEUE IS FULL.
ISEMPTY() − CHECKS IF THE QUEUE IS EMPTY.
IN QUEUE, WE ALWAYS DEQUEUE (OR ACCESS) DATA, POINTED BY FRONT POINTER AND
WHILE ENQUEING (OR STORING) DATA IN THE QUEUE WE TAKE HELP OF REAR POINTER.
ENQUEUE OPERATION
QUEUES MAINTAIN TWO DATA POINTERS, FRONT AND REAR. THEREFORE, ITS
OPERATIONS ARE COMPARATIVELY DIFFICULT TO IMPLEMENT THAN THAT OF STACKS.
THE FOLLOWING STEPS SHOULD BE TAKEN TO ENQUEUE (INSERT) DATA INTO A QUEUE −
STEP 1 − CHECK IF THE QUEUE IS FULL.
STEP 2 − IF THE QUEUE IS FULL, PRODUCE OVERFLOW ERROR AND EXIT.
STEP 3 − IF THE QUEUE IS NOT FULL, INCREMENT REAR POINTER TO POINT THE NEXT
EMPTY SPACE.
STEP 4 − ADD DATA ELEMENT TO THE QUEUE LOCATION, WHERE THE REAR IS POINTING.
STEP 5 − RETURN SUCCESS.
DEQUEUE OPERATION:
ACCESSING DATA FROM THE QUEUE IS A PROCESS OF TWO TASKS − ACCESS THE DATA
WHERE FRONT IS POINTING AND REMOVE THE DATA AFTER ACCESS. THE FOLLOWING
STEPS ARE TAKEN TO PERFORM DEQUEUE OPERATION −
STEP 1 − CHECK IF THE QUEUE IS EMPTY.
STEP 2 − IF THE QUEUE IS EMPTY, PRODUCE UNDERFLOW ERROR AND EXIT.
STEP 3 − IF THE QUEUE IS NOT EMPTY, ACCESS THE DATA WHERE FRONT IS POINTING.
STEP 4 − INCREMENT FRONT POINTER TO POINT TO THE NEXT AVAILABLE DATA
ELEMENT.
STEP 5 − RETURN SUCCESS.
LINKED LIST IMPLEMENTATION OF QUEUE:
DUE TO THE DRAWBACKS DISCUSSED IN THE PREVIOUS SECTION OF THIS TUTORIAL, THE ARRAY
IMPLEMENTATION CAN NOT BE USED FOR THE LARGE SCALE APPLICATIONS WHERE THE QUEUES ARE
IMPLEMENTED. ONE OF THE ALTERNATIVE OF ARRAY IMPLEMENTATION IS LINKED LIST
IMPLEMENTATION OF QUEUE.

THE STORAGE REQUIREMENT OF LINKED REPRESENTATION OF A QUEUE WITH N ELEMENTS IS O(N)

WHILE THE TIME REQUIREMENT FOR OPERATIONS IS O(1).
IN A LINKED QUEUE, EACH NODE OF THE QUEUE CONSISTS OF TWO PARTS I.E. DATA PART AND THE
LINK PART. EACH ELEMENT OF THE QUEUE POINTS TO ITS IMMEDIATE NEXT ELEMENT IN THE MEMORY.

INSERTION AND DELETIONS ARE PERFORMED AT REAR AND FRONT END RESPECTIVELY. IF FRONT AND
REAR BOTH ARE NULL, IT INDICATES THAT THE QUEUE IS EMPTY.
THE LINKED REPRESENTATION OF QUEUE IS SHOWN IN THE FOLLOWING FIGURE.
IN THE LINKED QUEUE, THERE ARE TWO POINTERS MAINTAINED IN THE MEMORY I.E. FRONT POINTER
AND REAR POINTER. THE FRONT POINTER CONTAINS THE ADDRESS OF THE STARTING ELEMENT OF THE
QUEUE WHILE THE REAR POINTER CONTAINS THE ADDRESS OF THE LAST ELEMENT OF THE QUEUE.
OPERATION ON LINKED QUEUE
THERE ARE TWO BASIC OPERATIONS WHICH CAN BE IMPLEMENTED ON THE LINKED
QUEUES. THE OPERATIONS ARE INSERTION AND DELETION.
INSERT OPERATION
THE INSERT OPERATION APPEND THE QUEUE BY ADDING AN ELEMENT TO THE END OF
THE QUEUE. THE NEW ELEMENT WILL BE THE LAST ELEMENT OF THE QUEUE.
FIRSTLY, ALLOCATE THE MEMORY FOR THE NEW NODE PTR BY USING THE FOLLOWING
STATEMENT.
PTR = (STRUCT NODE *) MALLOC (SIZEOF(STRUCT NODE));
THERE CAN BE THE TWO SCENARIO OF INSERTING THIS NEW NODE PTR INTO THE LINKED
QUEUE.
IN THE FIRST SCENARIO, WE INSERT ELEMENT INTO AN EMPTY QUEUE. IN THIS CASE, THE
CONDITION FRONT = NULL BECOMES TRUE. NOW, THE NEW ELEMENT WILL BE ADDED AS
THE ONLY ELEMENT OF THE QUEUE AND THE NEXT POINTER OF FRONT AND REAR
POINTER BOTH, WILL POINT TO NULL.
IN THE SECOND CASE, THE QUEUE CONTAINS MORE THAN ONE ELEMENT. THE CONDITION
FRONT = NULL BECOMES FALSE. IN THIS SCENARIO, WE NEED TO UPDATE THE END
POINTER REAR SO THAT THE NEXT POINTER OF REAR WILL POINT TO THE NEW NODE PTR.
SINCE, THIS IS A LINKED QUEUE, HENCE WE ALSO NEED TO MAKE THE REAR POINTER
POINT TO THE NEWLY ADDED NODE PTR. WE ALSO NEED TO MAKE THE NEXT POINTER OF
REAR POINT TO NULL.
REAR -> NEXT = PTR;
REAR = PTR;
REAR->NEXT = NULL;
IN THIS WAY, THE ELEMENT IS INSERTED INTO THE QUEUE.
SINGLY LINKED LIST OR ONE WAY CHAIN
SINGLY LINKED LIST CAN BE DEFINED AS THE COLLECTION OF ORDERED SET OF
ELEMENTS. THE NUMBER OF ELEMENTS MAY VARY ACCORDING TO NEED OF THE
PROGRAM. A NODE IN THE SINGLY LINKED LIST CONSIST OF TWO PARTS: DATA PART AND
LINK PART. DATA PART OF THE NODE STORES ACTUAL INFORMATION THAT IS TO BE
REPRESENTED BY THE NODE WHILE THE LINK PART OF THE NODE STORES THE ADDRESS
OF ITS IMMEDIATE SUCCESSOR.
ONE WAY CHAIN OR SINGLY LINKED LIST CAN BE TRAVERSED ONLY IN ONE DIRECTION. IN
OTHER WORDS, WE CAN SAY THAT EACH NODE CONTAINS ONLY NEXT POINTER,
THEREFORE WE CAN NOT TRAVERSE THE LIST IN THE REVERSE DIRECTION.
CONSIDER AN EXAMPLE WHERE THE MARKS OBTAINED BY THE STUDENT IN THREE
SUBJECTS ARE STORED IN A LINKED LIST AS SHOWN IN THE FIGURE.
IN THE ABOVE FIGURE, THE ARROW REPRESENTS THE LINKS. THE DATA PART OF EVERY NODE
CONTAINS THE MARKS OBTAINED BY THE STUDENT IN THE DIFFERENT SUBJECT. THE LAST NODE IN
THE LIST IS IDENTIFIED BY THE NULL POINTER WHICH IS PRESENT IN THE ADDRESS PART OF THE
LAST NODE. WE CAN HAVE AS MANY ELEMENTS WE REQUIRE, IN THE DATA PART OF THE LIST.
OPERATIONS ON SINGLY LINKED LIST:
THERE ARE VARIOUS OPERATIONS WHICH CAN BE PERFORMED ON SINGLY LINKED LIST. A LIST OF
ALL SUCH OPERATIONS IS GIVEN BELOW.
NODE CREATION
STRUCT NODE
{
INT DATA;
STRUCT NODE *NEXT;
};
STRUCT NODE *HEAD, *PTR;
PTR = (STRUCT NODE *)MALLOC(SIZEOF(STRUCT NODE *));
INSERTION
THE INSERTION INTO A SINGLY LINKED LIST CAN BE PERFORMED AT DIFFERENT
POSITIONS. BASED ON THE POSITION OF THE NEW NODE BEING INSERTED, THE INSERTION
IS CATEGORIZED INTO THE FOLLOWING CATEGORIES.
1 INSERTION AT BEGINNING IT INVOLVES INSERTING ANY ELEMENT AT THE FRONT OF
THE LIST. WE JUST NEED TO A FEW LINK ADJUSTMENTS TO MAKE THE NEW NODE AS THE
HEAD OF THE LIST.
2 INSERTION AT END OF THE LIST IT INVOLVES INSERTION AT THE LAST OF THE
LINKED LIST. THE NEW NODE CAN BE INSERTED AS THE ONLY NODE IN THE LIST OR IT
CAN BE INSERTED AS THE LAST ONE. DIFFERENT LOGICS ARE IMPLEMENTED IN EACH
SCENARIO.
3 INSERTION AFTER SPECIFIED NODE IT INVOLVES INSERTION AFTER THE SPECIFIED
NODE OF THE LINKED LIST. WE NEED TO SKIP THE DESIRED NUMBER OF NODES IN
ORDER TO REACH THE NODE AFTER WHICH THE NEW NODE WILL BE INSERTED.
DELETION AND TRAVERSING
THE DELETION OF A NODE FROM A SINGLY LINKED LIST CAN BE PERFORMED AT
DIFFERENT POSITIONS. BASED ON THE POSITION OF THE NODE BEING DELETED, THE
OPERATION IS CATEGORIZED INTO THE FOLLOWING CATEGORIES.
DOUBLY LINKED LIST
DOUBLY LINKED LIST IS A COMPLEX TYPE OF LINKED LIST IN WHICH A NODE CONTAINS A
POINTER TO THE PREVIOUS AS WELL AS THE NEXT NODE IN THE SEQUENCE. THEREFORE, IN
A DOUBLY LINKED LIST, A NODE CONSISTS OF THREE PARTS: NODE DATA, POINTER TO THE
NEXT NODE IN SEQUENCE (NEXT POINTER) , POINTER TO THE PREVIOUS NODE (PREVIOUS
POINTER). A SAMPLE NODE IN A DOUBLY LINKED LIST IS SHOWN IN THE FIGURE.

A DOUBLY LINKED LIST CONTAINING THREE NODES HAVING NUMBERS FROM 1 TO 3 IN THEIR
DATA PART, IS SHOWN IN THE FOLLOWING IMAGE.
IN A SINGLY LINKED LIST, WE COULD TRAVERSE ONLY IN ONE DIRECTION, BECAUSE EACH NODE
CONTAINS ADDRESS OF THE NEXT NODE AND IT DOESN'T HAVE ANY RECORD OF ITS PREVIOUS
NODES. HOWEVER, DOUBLY LINKED LIST OVERCOME THIS LIMITATION OF SINGLY LINKED LIST.
DUE TO THE FACT THAT, EACH NODE OF THE LIST CONTAINS THE ADDRESS OF ITS PREVIOUS
NODE, WE CAN FIND ALL THE DETAILS ABOUT THE PREVIOUS NODE AS WELL BY USING THE
PREVIOUS ADDRESS STORED INSIDE THE PREVIOUS PART OF EACH NODE.
MEMORY REPRESENTATION OF A DOUBLY LINKED LIST
MEMORY REPRESENTATION OF A DOUBLY LINKED LIST IS SHOWN IN THE FOLLOWING IMAGE.
GENERALLY, DOUBLY LINKED LIST CONSUMES MORE SPACE FOR EVERY NODE AND THEREFORE,
CAUSES MORE EXPANSIVE BASIC OPERATIONS SUCH AS INSERTION AND DELETION. HOWEVER,
WE CAN EASILY MANIPULATE THE ELEMENTS OF THE LIST SINCE THE LIST MAINTAINS
POINTERS IN BOTH THE DIRECTIONS (FORWARD AND BACKWARD).
IN THE FOLLOWING IMAGE, THE FIRST ELEMENT OF THE LIST THAT IS I.E. 13 STORED AT
ADDRESS 1. THE HEAD POINTER POINTS TO THE STARTING ADDRESS 1. SINCE THIS IS THE
FIRST ELEMENT BEING ADDED TO THE LIST THEREFORE THE PREV OF THE
LIST CONTAINS NULL. THE NEXT NODE OF THE LIST RESIDES AT ADDRESS 4 THEREFORE THE
FIRST NODE CONTAINS 4 IN ITS NEXT POINTER.
WE CAN TRAVERSE THE LIST IN THIS WAY UNTIL WE FIND ANY NODE CONTAINING NULL OR -1
IN ITS NEXT PART.
E –REFRENCES:
 HTTPS://WWW.GEEKSFORGEEKS.ORG/
 HTTPS://WWW.STUDYTONIGHT.COM/
 HTTPS://WWW.JAVATPOINT.COM/
 HTTPS://WWW.PROGRAMIZ.COM/
 HTTPS://WWW.COURSEHERO.COM/
 HTTPS://WWW.TUTORIALSPOINT.COM/
THANK YOU