Linked List

By
Muhammad Tasaddaq Latif
List Using Linked Memory
 Various cells of memory are not allocated
consecutively in memory.
 Not enough to store the elements of the list.
 With arrays, the second element was right next
to the first element.
 Now the first element must explicitly tell us
where to look for the second element.
 Do this by holding the memory address of the
second element
Linked List
 Create a structure called a Node.

object next

 The object field will hold the actual list element.

 The next field in the structure will hold the
starting location of the next node.
 Chain the nodes together to form a linked list.
Linked List
 Picture of our list (2, 6, 7, 8, 1) stored as a
linked list:

head

2 6 8 7 1 size=5

current
Linked List
Note some features of the list:
 Need a head to point to the first node of the list.
Otherwise we won’t know where the start of the
list is.
Linked List
Note some features of the list:
 Need a head to point to the first node of the list.
Otherwise we won’t know where the start of the
list is.
 The current here is a pointer, not an index.
Linked List
Note some features of the list:
 Need a head to point to the first node of the list.
Otherwise we won’t know where the start of the
list is.
 The current here is a pointer, not an index.
 The next field in the last node points to nothing.
We will place the memory address NULL which
is guaranteed to be inaccessible.
Linked List
 Actual picture in memory:
1051 6
1052 1063
current 1053 1063
1054 2
head 1055 1051
1056
2 6 8 7 1 1057 7
1058 1060
current 1059
1060 1
1061 0
head 1062 1054
1063 8
1064 1057
1065
Linked List
 Actual picture in memory:
1051 6
1052 1063
current 1053 1063
1054 2
head 1055 1051
1056
2 6 8 7 1 1057 7
1058 1060
current 1059
1060 1
1061 0
head 1062 1054
1063 8
1064 1057
1065
Building a Linked List
List list; headNode size=0
Building a Linked List
List list; headNode size=0

currentNode

headNode 2 size=1
list.add(2);
lastcurrentNode
Building a Linked List
List list; headNode size=0

currentNode

headNode 2 size=1
list.add(2);
lastcurrentNode

currentNode

list.add(6); headNode 2 6 size=2

lastcurrentNode
Building a Linked List

List.add(8); list.add(7); list.add(1);

currentNode

headNode 2 6 8 7 1 size=5

lastcurrentNode
Traversing
• (Traversing a Linked List) Let List be a linked list in
memory. This algorithm traverses List, applying an operation
process on each element of List. The variable PTR points to
the node currently being processed.
1- Set PTR=START[initializes pointer PTR]
2- Repeat Step 3 and 4 while PTR!=NULL
3- Apply Process to INFO[PTR]
4- Set PTR=Link[PTR] [PTR points next node]
[End of Step 2 Loop].
5- Exit.
C++ Code for Linked List
struct list
{ int data;
list* next;
}*f,*c,*p,*temp;

int t=0; //counter

void insert(void);
void print();
C++ Code for Linked List
int main()
{
system(“cls”);
insert();
print();
return 0;
}
C++ Code for Linked List
void insert(void) { else {
int ch=1; p->next=c;
while(ch==1) p=c;
{ cout<<"\n enter value";
c=new list(); cin>>c->data;
if(t==0) { }//else
f=c; cout<<"\n press 1 to enter another
p=c; node ";
cout<<"enter value"; cin>>ch;
cin>>c->data; t++;
c->next=NULL; } //end of while
}//if // if(ch!=1)
c->next=NULL;

} // end of insert
void print(void) {
Temp = f ;
cout<<"\n value of link list ";

while(temp->next!=NULL) {
cout<<temp->data<<" “<<temp->next;
temp=temp->next;
} end of while
cout<<temp->data<<" ";
}
C++ Code for Linked List

int get() {
if (currentNode != NULL)
return currentNode->get();
};
C++ Code for Linked List
bool next() {
if (currentNode == NULL) return false;

lastCurrentNode = currentNode;
currentNode = currentNode->getNext();
if (currentNode == NULL || size == 0)
return false;
else
return true;
};
Analysis of Linked List
 add
• we simply insert the new node after the current
node. So add is a one-step operation.
Analysis of Linked List
 add
• we simply insert the new node after the current
node. So add is a one-step operation.
 remove
 remove is also a one-step operation
Analysis of Linked List
 add
• we simply insert the new node after the current
node. So add is a one-step operation.
 remove
 remove is also a one-step operation
 find
 worst-case: may have to search the entire list
Analysis of Linked List
 add
• we simply insert the new node after the current
node. So add is a one-step operation.
 remove
 remove is also a one-step operation
 find
 worst-case: may have to search the entire list
 back
 moving the current pointer back one node requires
traversing the list from the start until the node whose
next pointer points to current node.