I want to change some pointers around in a linked list, and I was wondering if I could use the STL list for the purpose.
I want to do something like this:
Is it possible with stl?
2 Likes
There’s no stl method for rotating a linked list, however you can do this with a std:vector.
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> l;
vector<int> :: iterator it;
l.push_back(1);
l.push_back(2);
l.push_back(3);
l.push_back(4);
l.push_back(5);
rotate(l.begin(), l.begin()+2, l.end()); //stl rotation
for(it=l.begin(); it!=l.end(); it++) {
cout << *it << " ";
}
return 0;
}
Please correct me if I am wrong.
1 Like
//l is initial list here list. I first copy those values in a temporary list then and erase them from initial list. Then I inserted //them in front from l.begin() that is in front.
list <int> temp(find(l.begin(), l.end(), 3), l.end());
l.erase(find(l.begin(), l.end(), 3), l.end());
l.insert(l.begin(), temp.begin(), temp.end());
If you already have the iterator to the position in the middle where you want to make the cut, you can do this in O(1) in an C++ STL list using splice.
1 Like
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct sllist
{
int data;
struct sllist *next;
};
struct sllist head=NULL;
void insert(int data,int position);
void Delete(int position);
void display(void);
void change(void);
int main()
{
int p,ps;
char con;
printf(“Enter a Number:”);
scanf("%d",&p);
head=(struct sllist)malloc(sizeof(struct sllist));
head->data=p;
head->next=NULL;
do
{
printf("\nFOR INSERTION PRESS i");
printf("\nFOR DISPLAY PRESS d");
printf("\nFOR EXIT PRESS e");
printf("\nFOR YOUR CHOICE:");
con=getche();
printf("\n");
switch(con)
{
case ‘i’:
{
printf(“ENTER DATA:”);
scanf("%d",&p);
printf(“ENTER POSITION:”);
scanf("%d",&ps);
insert(p,ps);
break;
}
case ‘d’:
{
display();
break;
}
}
}while(con!=‘e’);
change();
display();
}
void insert(int data,int position)
{
struct sllist temp,node;
if(position==1)
{
temp=(struct sllist)malloc(sizeof(struct sllist));
temp->data=data;
temp->next=head;
head=temp;
return;
}
else
{
temp=head;
int i=2;
while((temp->next!=NULL)&&(i++<position))
temp=temp->next;
if(i<position)
{
printf("\nGIVEN POSITION DOES NOT EXIST");
return;
}
node=(struct sllist)malloc(sizeof(struct sllist));
node->data=data;
node->next=temp->next;
temp->next=node;
}
}
void display(void)
{
struct sllist *temp=head;
while(temp!=NULL)
{
printf("%d\t",temp->data);
temp=temp->next;
}
}
void change(void)
{
struct sllist *temp=head,*temp1=head->next;
while(temp->next!=NULL)
temp=temp->next;
temp->next=head;
head=temp1->next;
temp1->next=NULL;
}
Blockquote
The rotate method, as far as I can tell, should be O(n) and will beat the purpose of using a linked list for the task.
The only way to achieve this in O(1) time is to use a custom linked list then?
I think a custom linked list can not complete this task in constant O(1) time. In worst case you have to perform n operations/swaps. Take a look at this link and share you views. Meanwhile let me try this with custom linked list.
I think it can, you only have to delete one pointer (2->3), and add one pointer(5->1). But then I suppose finding those pointers will take linear time, so you can only do it in constant time if you already have a reference to those particular pointers. Finding and creating (5->1) should be O(1), but searching for (2->3) will indeed be O(n)
1 Like
That was a typo…
You can reach at the pointer in constant time using
advance(it, distance) if you use random-access iterators.
Time complexity is constant for random-access iterators.
swap_ranges, copy, copy_n, fill_n every function takes O(n) time.
1 Like
Thing is, linked lists are not random access. So it’d take O(n) to find the pointer.
1 Like
off course 
:thumsup
1 Like
~Thanks for the help!
Of course it’s possible in O(n) time, I wanted to ask whether the operations were possible in O(1) time.