3. Data structures and algorithms - Linked List.pdf.pdf

interview and college curated linked list DSA in C language

1. Data Structures and Algorithms (CS-2001)
KALINGA INSTITUTE OF INDUSTRIAL
TECHNOLOGY
School of Computer Engineering
4 Credit Lecture Note
Strictly for internal circulation (within KIIT) and reference only. Not for outside circulation without permission

2. Chapter Contents
School of Computer Engineering
Sr #Major andDetailed Coverage Area Hrs
3Linked List 8
Singly Linked Lists and Chains, Representing
Chains in C, Polynomials, Sparse Matrix,
Doubly Linked Lists,Circular & Header
Linked Lists
2

3. Linked List
School of Computer Engineering
LinkedLististhelineardatastructurewhichareconnectedtogethervialinksandisa
sequenceofnodeswhichcontainsitemsandconnectiontoanothernode.Itisthe
secondmostuseddatastructureafterarray.
ImportantConcepts:
Node−Eachnodeofalinkedliststoreadatacalledanelement.
Next−EachLinkofalinkedlistcontainalinktonextlinkcalledNext.
Head−ALinkedListcontainstheconnectionlinktothefirstnode.Thiscanalsobe
termedasstart.
Linkedlistcanbevisualizedasachainofnodes,whereeverynodepointstothenext
node.
3

4. Linked List Example
School of Computer Engineering
4

5. Linked List Advantages, Disadvantages and Applications
School of Computer Engineering
Theyareadynamicinnaturewhichallocatesmemorywhenrequired.
Insertionanddeletionoperationscanbeeasilyimplemented.
Stacksandqueuescanbeeasilyexecuted.
LinkedListreducestheaccesstime.
Advantages
Thememoryiswastedaspointersrequireextramemoryforstorage.
Noelementcanbeaccessedrandomly;ithastoaccesseachnodesequentially.
Reversetraversingisdifficultinlinkedlist.
Disadvantages
Needwhereinitialsizeisunknown
Needtoinsertelementsatthebeginningor/andendofthelist
Usedtoimplementstacks,queues,graphs,etc
Applications
5

6. Linked List Representation
School of Computer Engineering
Inmemorythelinkedlistisstoredinscatteredlocations.Thememoryforeachnodeis
allocateddynamicallyi.e.asandwhenrequired.SotheLinkedListcanincreaseasper
theuserwishandthesizeisnotfixed,itcanvary.
Supposefirstnodeoflinkedlistisallocatedwithanaddress1008.Itsgraphical
representationlookslike:
Supposenextnodeisallocatedatanaddress506,sothelistbecomes
Supposenextnodeisallocatedwithanaddress10andthelistbecomes
Address Comments Next
e.g. 8005 Root & single node 1008
1008 2
nd
node insertion 506
506 3
rd
node insertion 10
6

7. Linked List Representation –structure based
School of Computer Engineering
Declarationofstructthatshouldbeusedtocreatealistwhereeachnode
holdsinfo.
structnode
{
intinfo;
structnode*next;
};
Thenextstepistodeclareapointertoserveasthelisthead,i.e.
structnode*head;
OncenodedatastructureisdeclaredandhavecreatedaNULLheadpointer,
anemptylinkedlistiscreated.
Thenextstepistoimplementoperationswiththelist.
7

8. Linked List Representation –Array based
School of Computer Engineering
LetLISTbethelinkedlistandwillbe
maintainedinmemory.Firstofall,LIST
requirestwolineararrays–callthemasINFO
andLINK.INFO[K]representstheinformation
partandLINK[K]representsthenextpointer
fieldofthenodeofLISTforK
th
element.LIST
alsorequires2variablessuchasSTARTwhich
containsthelocationofthebeginningofthelist
andthenextpointersentineldenotedby
NULLwhichindicatestheendofthelist.
SincethesubscriptofthearraysINFOandLINK
willusuallybepositive,soNULLshouldbe
treatedas0unlessotherwisestated.
Note: representsblankcharacterinthepicture
8

9. Example
22
74
77
82
51
10
11
27
1
2
3
4
5
6
7
8
9
ROLL NO
9
4
8
3
1
6
0
0
LINK
2
7
Boy CR
Girl CR
9
School of Computer Engineering

10. Class Work
Supposethepersonnelfileofasmallcompanycontainsthefollowingdataofits
employees:Name,EmployeeNo,Sex,Salary.Designalinkedlistusingarrays.
SofourparallelarrayssayName,
EmpNo,Sex,Salaryarerequired
tostorethedata.Additionally,
parallelarrayLINKisrequired
forthenextpointerfieldofthe
listandthevariableHEADisto
pointtothe1
st
recordinthelist.
0canbeusedtorepresentthe
nullpointer.
10
School of Computer Engineering
Name LINKEmpNoSex Salary
Solution
Head

11. Class Work
Supposethepersonnelfileofasmallcompanycontainsthefollowingdataofits
employees:Name,EmployeeNo,Sex,Salary.Designalinkedlistusingstructure.
structpersonnel
{
char*name;
intemp_no;
charsex;
floatsalary;
structpersonnel*next;
}
structpersonnel*head;
11
School of Computer Engineering
Solution
8080
head
A 1 M 107080
8080
B 2 F 20NULL
7080

12. Types of Linked List
School of Computer Engineering
SingleLinkedList−Itemnavigationisforwardonly.Alsocalledasone-waylist
DoubleLinkedList−Itemscanbenavigatedforwardandbackwardway
CircularLinkedList−Lastitemcontainslinkofthefirstelementasnextandfirst
elementhaslinktolastelementasprev.
Chains–Achainisalinkedlistinwhicheachnoderepresentsoneelement
Two-WayLists–DoubleandCircularLinkedList
12
Circular, singly linked list
Circular, doubly linked list

13. Double Linked List
School of Computer Engineering
DoublyLinkedListisavariationofLinkedlistinwhichnavigationispossibleinboth
waysi.e.eitherforwardandbackward.
ImportantConcepts:
Node−Eachnodeofalinkedliststorethedata
Next−Eachnodeofalinkedlistcontainalinktonextlink
Prev−Eachnodeofalinkedlistcontainalinktopreviouslink
LinkedList−ALinkedListcontainstheconnectionlinktothefirstLinkcalledFirst
andtothelastlinkcalledLast.FirstisalsocalledasHeadandLastisalsocalledas
Tail.
13

14. Circular Linked List
School of Computer Engineering
CircularLinkedListisavariationofLinkedlistinwhichfirstelementpointstolastelementandlastelementpoints
tofirstelement.BothSinglyLinkedListandDoublyLinkedListcanbemadeintoascircularlinkedlist.
Singly Linked List as Circular
Insinglylinkedlist,thenextpointerofthelastnodepointstothefirstnode.
Doubly Linked List as Circular
Indoublylinkedlist,thenextpointerofthelastnodepointstothefirstnodeandtheprevious
pointerofthefirstnodepointstothelastnodemakingthecircularinbothdirections.
14

15. Linked List Basic Operation
School of Computer Engineering
Insertion−addanelementatthebeginningofthelist.
Deletion−deleteanelementatthebeginningofthelist.
InsertLast-addanelementintheendofthelist.
DeleteLast−deleteanelementfromtheendofthelist.
InsertAfter−addanelementafteranitemofthelist.
Traverse−Traverseanddisplaythecompletelistinforward
manner.
Search−searchanelementusinggivenkeyordataitem.
Delete−deleteanelementusinggivenkeyordataitem.
TraverseBackward−displayingcompletelistinbackward
manner.Applicablefordoubleandcircularlinkedlist
15

16. Node Structure and Chain Formation
School of Computer Engineering
Considerthesinglylinkedlistnodestructureasfollows:
structnode
{
intdata;
structnode*next=NULL;
}*head=NULL;
CreationoftheList:
voidCreate()
{
structnode*link=(structnode*)malloc(sizeof(structnode));
scanf(“%d”,&link->data);
link->next=head;
head=link;
}
16

17. Traversal
School of Computer Engineering
Traversinglinkedlistmeansvisitingeachandeverynodeofthesinglylinkedlist.Followingstepsare
involvedwhiletraversingthesinglylinkedlist–
1.Firstlymovetothefirstnode
2.Fetchthedatafromthenodeandifrequired,performtheoperationssuchasarithmeticoperation
oranyoperationdependingondatatype.
3.Afterperformingoperation,advancepointertonextnodeandperformallabovestepsonvisited
node.
Pseudocode:
voidtraverse()
{
structnode*temp=start;//MovetoFirstNode
do
{
printf(“%d”,temp->data);
temp=temp->next;//MovePointertoNextNode
}while(temp!=NULL);
}
17
Class Work
DesignsearchalgorithmforSLL(Single
LinkedList)

18. Insertion at Start
School of Computer Engineering
InsertinganodeatstartintheSLL(SingleLinkedList):
1.CreateNewNode
2.FillDatainto“DataField“
3.Makeit’s“Pointer”or“NextField”asNULL
4.AttachThisnewlyCreatednodetoHead
5.MakenewnodeasStartingnode
Pseudocode:
structnode*new_node;
new_node=(structnode*)malloc(sizeof(structnode));
scanf(“%d”,&new_node->data);
if(head==NULL)
head=new_node;
else
{
new_node->next=head;
head=new_node;
}
18

19. Insertion at Last
School of Computer Engineering
InsertinganodeatlastintheSLL(SingleLinkedList):
1.CreateNewNode
2.FillDatainto“DataField“
3.Makeit’s“Pointer”or“NextField”asNULL
4.NodeistobeinsertedatLastPositionsoweneedtotraverseSLLuptoLastNode.
5.Makelinkbetweenlastnodeandnewnode
Pseudocode:
structnode*new_node=(structnode*)malloc(sizeof(structnode));
scanf(“%d”,&new_node->data);
if(head==NULL)
head=new_node;
else
{
structnode*temp=NULL;
for(temp=head;temp->next!=NULL;temp=temp->next);
temp->next=new_node;
}
19

20. Insertion at Specific Position
School of Computer Engineering
InsertinganodeatlastintheSLL(SingleLinkedList):
1.CreateNewNode
2.FillDatainto“DataField“
3.Makeit’s“Pointer”or“NextField”asNULL
4.NodeistobeinsertedatgivenPositionsoweneedtotraverseSLLuptogivenposition.
5.Makelinkbetweenspecificpositionnodeandnewnode
Pseudocode:
structnode*new_node=(structnode*)malloc(sizeof(structnode));
scanf(“%d”,&new_node->data);
intpos;
scanf(“%d”,&pos);
if(head==NULL)
head=new_node;
else
{
structnode*temp=NULL;inti=1;
for(temp=head;i<pos-1;temp=temp->next,++i);
structnode*temp1=temp->next;temp->next=new_node;new_node->next=temp1;
}
20

21. Deletion
School of Computer Engineering
PseudocodeforDeleteFirstNodefromSinglyLinkedList:
structnode*temp;
temp=head;
head=head->next;
free(temp);
PseudocodeforDeleteLastNodefromSinglyLinkedList:
structnode*temp=head,t=NULL;
if(head->next==NULL)
{
free(head);
head=NULL;
}
else
{
for(;temp->next!=NULL;temp=temp->next,t=temp);
free(t->next);
t->next=NULL;
}
21
Class Work
Designanalgorithmtodeleteanodeata
specifiedposition
Designarecursivealgorithmtocount
numberofnodesinSLL

22. Linked List Implementation
School of Computer Engineering
Singly Linked List Double Linked List
22
Singly Linked List as Circular

23. Header Linked List
School of Computer Engineering
Headerlinkedlistisalinkedlistwhichalwayscontainsaspecialnode
calledtheHeaderNode,atthebeginningofthelist.Itdoesnotcontain
actualdataitemincludedinthelistbutusuallycontainssomeuseful
informationabouttheentirelinkedlist.Ithastwotypes:
1.GroundedHeaderLinkList−LastNodeContainstheNULLPointer
2.CircularHeaderLinkList−LastNodePointsBacktotheHeader
Node.
Note:Start/HeadalwayspointstoHeaderNode.
23

24. Header Linked List Implementation
School of Computer Engineering
Grounded Header Link List
24
Class Work
Writecreationanddisplaymethodof
CircularHeaderLinkList

25. Polynomials
School of Computer Engineering
Polynomialisanexpressionconstructedfromoneormorevariablesandconstants,
usingonlytheoperationsofaddition,subtraction,multiplication,andconstantpositive
wholenumberexponents.Atermismadeupofcoefficientandexponent.
Examples–
Polynomial with single variable P(X) = 4X
3
+ 6X
2
+7X+9 (4,6,7are coefficient & 3,2
are exponent)
Polynomial with 2 variables P(X, Y) = X
3
-2XY +1 (2is coefficient & 3is exponent)
Definition–
Polynomial with single variable P(X) =
Polynomial can be represented using Linked List in 2 ways namely:
1.Single Linked List
2.Header linked list
25

26. Single Linked List Polynomial Representation
School of Computer Engineering
Nodeofapolynomial:
Forexample,P(X)=4X
3
+6X
2
+7X+9isrepresentedas
26
CoefficientExponentNext
43 62 71 90
Ineachnodetheexponentfieldwillstorethecorrespondingexponentandthe
coefficientfieldwillstorethecorrespondingcoefficient.Linkfieldpointstothenextitem
inthepolynomial.
Points to keep in mind
1.Thesignofeachcoefficientandexponentisstoredwithinthecoefficientandthe
exponentitself
2.Thestorageallocationforeachterminthepolynomialmustbedoneindescending
orderoftheirexponent

27. School of Computer Engineering
Letp(x)denotethefollowingpolynomialinonevariable(containing
fournonzeroterms):P(x)=2x
8
–5x
7
–3x
2
+4.Itmayberepresentedby
theheaderlistshownbelowwhereeachnodecorrespondstoanonzero
termofp(x).Specifically,theinformationpartofthenodeisdividedinto
twofieldsrepresentingthecoefficientandtheexponentofthe
correspondingtermandthenodesarelinkedaccordingtodecreasing
degreeoftheexponent.Theheadernodeisneededtorepresentthezero
polynomial(i.e.apolynomialwiththevaluezero(0)isknownaszero
polynomial)
27
Header Linked List Polynomial Representation

28. Sparse Matrix
School of Computer Engineering
Asparsematrixisatwo-dimensionalarrayinwhich
mostoftheelementsarezeroornull.Itisawastageof
memoryandprocessingtimeifwestorenullvaluesor0
ofthematrixinanarray.Toavoidsuchcircumstances
differenttechniquesareusedsuchaslinkedlist.
N-squaresparsematricesiscalledtriangular
matrix.Asquarematrixiscalledlower
triangularifalltheentriesabovethemain
diagonalarezero.Similarly,asquarematrixis
calleduppertriangularifalltheentriesbelow
themaindiagonalarezero.
28

29. Sparse Matrix cont…
School of Computer Engineering
Sparsematrixcanberepresentedusingalistofsuchnodes,oneper
non–zeroelementofthematrix.Forexample,considerthesparsematrix
Thelinkedlistcanberepresentedusinglinkedlistasshownbelow
29
Class Work
Designnon-arraybaseddatastructuretorepresentlowertriangular,upper
triangularandtri-diagonalmatrix.

30. Assignments
School of Computer Engineering
1.Designalgorithm/developpseudocode/writeCcodetoaddagivenvalueKtoeachelementin
theLIST.
2.Designalgorithm/developpseudocode/writeCcodetodeletesthelastnodefromtheLIST.
3.Designalgorithm/developpseudocode/writeCcodetodeletethe1
st
nodefromthelist.
4.Designalgorithm/developpseudocode/writeCcodewhichinterchangestheK
th
andK+1
st
elements
5.Designalgorithm/developpseudocode/writeCcodetoswapnodesinalinkedlistwithout
swappingdata.
6.Designalgorithm/developpseudocode/writeCcodetoreversethenodesinalinkedlist.
7.Designalgorithm/developpseudocode/writeCcodetocreatealinkedlistfromagivenlinked
list.Thenewlinkedlistmustcontaineveryalternateelementoftheexistinglinkedlist.
8.Designalgorithm/developpseudocode/writeCcodetocountthenumberoftimesagivenkey
occursinalinkedlist
9.Letalinkedlistconsistsofnnumberofnodes,whereeachnodeconsistsofanuniquenumber,a
prioritynumber(inbetween1to5),andpointertonextnodeDesignthealgorithm/develop
pseudocode/writeCcodetodividethenodesintodifferentlinkedlistwhereeachlinked
consistsofnodeshavingsamepriority.
30

31. Assignments
School of Computer Engineering
31
10.Designalgorithm/developpseudocode/writeCcodetodeletennodesaftermnodes
ofalinkedlist
11.Designalgorithm/developpseudocode/writeCcodetocheckifasinglylinkedlistis
palindrome
12.Designalgorithm/developpseudocode/writeCcodetosearchanelementinalinked
list,iffounddeletethatnodeandinsertthatnodeatbeginning.Otherwisedisplayan
appropriatemessage.
13.Designalgorithm/developpseudocode/writeCcodetoadd,subtractandmultiply2
polynomials.
14.Designalgorithm/developpseudocode/writeCcodetodeletelastoccurrenceofan
itemfromlinkedlist
15.GivenasinglylinkedlistwithnodesL0->L1->…->Ln-1->Ln.Designthe
algorithm/developpseudocode/writeCcodetorearrangethenodesinthelistso
thatthenewformedlistis:L0->Ln->L1->Ln-1->L2->Ln-2…

32. School of Computer Engineering
32

33. Home Work (HW)
1.Designalgorithm/developpseudocode/writeCcodetodeletethewholelinkedList
2.Designalgorithm/developpseudocode/writeCcodetofindk
th
nodefromtheendof
alinkedlist
3.Designalgorithm/developpseudocode/writeCcodetomergetwosortedlinkedlists
andcreateasortedlinkedlist.
4.Designalgorithm/developpseudocode/writeCcodetodeletealternatenodesofa
linkedlist.
5.algorithm/developpseudocode/writeCcodetofindtheunionoftwolinkedlist
6.Designalgorithm/developpseudocode/writeCcodetofindthedifferenceoftwo
linkedlist
7.Designalgorithm/developpseudocode/writeCcodetofindtheintersectionoftwo
linkedlist
8.Designalgorithm/developpseudocode/writeCcodetodeleteallduplicatenodes
fromadoublycircularlinkedlist.
9.Designalgorithm/developpseudocode/writeCcodetodeleteconsecutivetwonodes
fromadoublylinkedlistbasedonthegivenposition
10.Designalgorithm/developpseudocode/writeCcodetoaddtwosparsematrices,
multiplytwomatrices,transposeamatrix
33
School of Computer Engineering

34. Supplementary Reading
http://www.geeksforgeeks.org/data-structures/linked-list/
https://www.tutorialspoint.com/data_structures_algorithms/linked_list_alg
orithms.htm
http://www.studytonight.com/data-structures/introduction-to-linked-list
http://nptel.ac.in/courses/106103069/8
https://www.tutorialspoint.com/learn_c_by_examples/linked_list_programs
_in_c.htm
34
School of Computer Engineering

35. FAQ
WhatisLinkedList?
alinkedlistisalinearcollectionofdataelements,inwhichlinearorderis
notgivenbytheirphysicalplacementinmemory.Eachpointingtonextnode
bymeansofapointer.Itisadatastructureconsistingofagroupofnodes
whichtogetherrepresentasequence.Underthesimplestform,eachnodeis
composedofdataandareference(inotherwords,alink)tothenextnodein
thesequence.Thisstructureallowsforefficientinsertionorremovalof
elementsfromanypositioninthesequenceduringiteration.Morecomplex
variantsaddadditionallinks,allowingefficientinsertionorremovalfrom
arbitraryelementreferences.
35
School of Computer Engineering

36. FAQ
LinkedListADT
ADTconsistsofthefollowingprimitiveoperations:
Create()
Destroy()
Add(element)
Remove(element)
Traverse()
IsEmpty()
Search(element)
RemoveloopinLinkedList
WriteafunctionthatcheckswhetheragivenLinkedListcontainsloopandif
loopispresentthenremovestheloopandreturnstrue.Andifthelistdoesn’t
containloopthenreturnsfalse.Abovediagramshowsalinkedlistwitha
loop.Onpassingittothefunction,itshouldmodifythebelowlistto1->2->3-
>4->5->NULL.
36
School of Computer Engineering