Linked Lists
For Princess Only :O :) :)
Saturday 17 September 2011
What are we studying? Ans: Data Structures
Saturday 17 September 2011
So what is a linked list? Ans: It is a data structure... SIMBLE!
Saturday 17 September 2011
Denition
A linked list is a data structure consisting of a group of
nodes, which together represent a sequence!
the se thin gs are onl y the nod es!
this thingy is called a terminator... ( asta la vista baby :p ) this is used to signify the end of the list!
ooooohhh... a picture of a linked list!!
So how many nodes does this linked list have? Ans: Three :) :) :)
** This is only half the denition :o
Saturday 17 September 2011
Denition++
Each node consists of a DATA and a REFERENCE
to the next node in the linked list
And also the image on top is just a graphical representation you wanna know how it actually looks in the computer? :o
Saturday 17 September 2011
Computer Memory
Address : 001 Address : 002 Address : 003 Address : 004 Address : 005 Address : 006
12 003
99 005
37
Address of next node
this is how a linked list looks in memory
each of the boxes is a memory cell with an address :)
As you can see in a computer there are no arrows :P basically it just holds the address to the next memory cell which has the data :)
Saturday 17 September 2011
But why is knowing how a linked list looks in memory so important? :O Because when we write algorithms me manipulate the addresses of the linked list and nothing else :)
Saturday 17 September 2011
If you were able to follow this much without much confusion say Chilipiga on the phone :P
Saturday 17 September 2011
Woggay! Time to look at algorithms! :P
Saturday 17 September 2011
Basic Denitions to Understand Algorithms
what do the different variables mean? :O
pHead
pointer to head of the linked list
pLoc
pointer pointing t current node
lets say Chandler, rachel, ross, monica, joey and phoebe are a linked list if you want to acces only monica form the list... the address of monica would be stored in pLoc
Saturday 17 September 2011
pPre pLoc
pNext
pNext pNext is the pointer pointing to the next node that means -> if pLoc points to Monica pNext would point to Joey! AND pPre would point to Ross! :O
Saturday 17 September 2011
So Always remember in the algorithms pLoc points to the current node pNext points to the next node pPre points to the previous node :) :)
Saturday 17 September 2011
Algorithms Time :o
Saturday 17 September 2011
algorithm insertNode
Saturday 17 September 2011
So this is our algorithm!
What is it doings?
a. First it checks if the list has any elements If the list is empty it inserts the data in the list head b. if the list is not empty.. it adds the data to the end of the list
thats all is the main logic! :o
Saturday 17 September 2011
Ok lets break this down :)
this is rst part of all linked list algorithms
in our case is - insertnode
the general format is
algorithm name of the algorithm ( whatever we want to input into algorithm ) now lets look at types of data we input
for pPre / pNext / pLoc (anything with p at the begining the general way to write is val pPre / pNext / pLoc <nodePointer>
if there is a p nodePointer will always come and val will always come remember!
Saturday 17 September 2011
Every linked list algorithm will have ref list <metadata> as the rst line
Saturday 17 September 2011
what is this? its also very simble! if we want to create a new pointer variable in our algorithm we use this command allocate(pNew) we can do ilke this also allocate(pNews) allocate(pBoring) any name you can give provided you use the same through out the program :)
Saturday 17 September 2011
But why are we using it here? :O Because we are putting something new something that wasnt there before into the linked list thats why we use pNew in algorithms where we are not putting anything new in the linked list we dont use the pNew pointervariable and ** as i said before anything that starts with p is a pointer variable. :)
Saturday 17 September 2011
Logic
Saturday 17 September 2011
Condition 1: Linked list doesnt have any elements only [Link] is there
Saturday 17 September 2011
But rst lets understand list head :O List head has 2 parts 0 001
Count Head
Count: This contains the number of nodes in the linked list Head: this contains the address of the rst element in the linked list ** All linked lists will have a head and a Terminator in the end.
Saturday 17 September 2011
So what happens when we have a linked list without anything in it? 0 001
Count Head
It looks like this only... itll have a head and a terminator! So to put a node into it we must do a simple thig we must make the head point to pNew (the node we want to insert) and we must make pNew point to the terminator 0 002
Count Head
13 001
Saturday 17 September 2011
So this is logic :) rst it checks if the linkedlist is empty that is done by if(pPre NULL) and if that is true pNew -> link = [Link] [Link] = pNew
// Null means zero or nothing and this actually reads as if( pPre == NULL)
Saturday 17 September 2011
Condition 2: If linked list is already having a few/many elements
Saturday 17 September 2011
So lets say FRIENDS are a linked list Ross points to phoebe, phoebe points to joey, joey to monica and monica to chandler
But wait rachell is missing :o :( she was late for photo shoot! :( So now we have to insert rachel in between the other friends how do we do it? :o
Saturday 17 September 2011
pPre pPre -> link
So lets say we want to put rachell in between phoebe and joey what do we do? We make phoebe point to rachel and rachel point to joey.... now if rachel is pNew pPre is phoebe so pNew should point to joey... now pPre was already pointing to joey so if i do pNew -> link = pPre -> link pNew points to whatever pPre was pointing to and now we must make pPre point to pNew so we do pPre -> link = pNew
Saturday 17 September 2011
Now all friends are together :)
Saturday 17 September 2011
So now that you understood the logic lets try to easily remember the algorithm :) Lets Break it Down
Initialisation Variable Declaration This is a simple checking condition to see if memory is available to continue running the program Remember the new node were inserting? In this line we assign what data to put in the node that data is got from the arguments passsed into the algorithm at the initialisation stage
Main Logic of the algorithm
in insert algorithm since we are adding an element we increment the list count by 1 in deletion we will decrement by 1 return true is the second last line in all algorithms and last line is always end algorithm name
Saturday 17 September 2011
1. Initialisation Q: What does this algorithm do? A: It inserts a new node into a linked list Q:For that what do we need? A: We need a linked list a node after which to insert our new node data for the new node
A linked list a node after which to insert our new node data for the node
So thats what this part is doing :)
Saturday 17 September 2011
[Link] Decleration
we create a new node to be inserted into the linked list ** this is only half of the process, in this step weve only created a new node we havent given it any data yet. that happens in line #11 so this is only half the process
Saturday 17 September 2011
3. Checking
Just check to see if it is possible to continue with the program if not it says return false return false na basically the program cant run
Saturday 17 September 2011
[Link] decleration Part 2
here we are simply putting the data into the node we created earlier pNew
Saturday 17 September 2011
5. Main Logic
I hope after seeing the examples this is easy to understand now :)
Saturday 17 September 2011
6. Finishing Step
here we just incrememnt count value and nish the linked list
Saturday 17 September 2011
7. End
these two lines come in almost all algorithms at the end
Saturday 17 September 2011
Initialisation Variable Decleration Checking Variable Decleration Main Logic Finishing Step End I guess you are better at making full forms then me :P
Saturday 17 September 2011
