Hey .... i'd like to write an algorithm that can reverse singly Linked List without using any other type of data structures suck as stacks, arrays, queue .... etc
i mean this algorithm have to be created only by using Linked List interface .
i've created one... but the problem is that it's O(n^2) ... so can anyone help with writting this algorithm to be O(n) ..
Thanks.
sathupally
October 10th, 2004, 08:14 PM
Is it singly linked list or doubly?
HypnotiC
October 11th, 2004, 12:48 AM
Hey Sathupally ...
the liked list is Singly ...
it would be great if u can help with code.
take into your account u should not use any other data structures such as stacks,
arrays, queue.....etc .. and also dont use any java library ...
just use Linked List interface
HypnotiC
October 11th, 2004, 01:01 AM
this is the code of the singly linked list ...
you have just to use this interfce to write the algorithm
public class LinkList {
int size;
Node head;
Node tail;
public LinkList() {
size = 0;
head = null;
tail = null; }
public int size()
{
return size;
}
public boolean isEmpty()
{
return (size==0);
}
public void add(int x,String y)
{
Node n1 = new Node(x,y,null);
if(size==0)
head = n1;
else
tail.setNext(n1);
tail = n1;
size++;
}
public void Delete(int x)
{
if (x < 1 || x > size())
{
System.out.println(" index out of boundary ");
return;
}
if (x==1)
{
Node n1 = head;
head = head.getNext();
n1.setNext(null);
Take a look at this. It only takes head as the parameter and calculate the size and tail itself. Since you already have them, so you can eliminate it and use the rest.
Hi HypnotiC!
For an easy reading, when posting source code, please embrace it in tags, as described here (http://www.codeguru.com/forum/misc.php?do=bbcode).
Please read my comments on the code you've posted:public class LinkList {
// Bornish: why having a "size" member data?
int size;
Node head;
Node tail;
public LinkList() {
size = 0;
head = null;
tail = null;
}
public int size() {
return size;
}
public boolean isEmpty() {
return (size==0);
}
// Bornish: adding to the head of the list would be faster
public void add(int x,String y) {
Node n1 = new Node(x,y,null);
if(size==0)
head = n1;
else
tail.setNext(n1);
tail = n1;
size++;
}
// Bornish: more useful to have a delete by ID, not by index
public void Delete(int x) {
if (x < 1 || x > size()) {
System.out.println(" index out of boundary ");
return;
}
if (x==1) {
Node n1 = head;
head = head.getNext();
// Bornish: what is next line supposed to do?
n1.setNext(null);
}
else {
// Bornish: what will tail be when x==size?
Node n1 = head;
for(int i = 1; i< x-1; i++) {
n1 = n1.getNext();
}
n1.setNext (n1.getNext().getNext());
// Bornish: next line breaks the list by
// replacing what the above line just did
n1.setNext(null);
}
size--;
}
}I don't see the point in maintaining the member data size,...
Also, makes no sense to create a node having an integer ID by passing "x" parameter to an add functionality, but then delete a node by considering "x" being the index in the list, not the ID.
Is it required that you add nodes to your list at the tail? I'm asking because it's much faster to add at the head of the list. Anyhow, you could implement both addHead() and addTail(), and use the appropriate. If your implementation already uses a huge number of add() calls, then you can keep it, by calling inside the one method which you'd like to have as default.
Try to delete the last element of your list (x==size), and you'll notice that tail member data will not be anymore a valid node of the list.
Deleting an element in the middle of the list will break the list connection because of the line highlighted in red.
Since you forgot to mention how the reversed list should be returned, I have implemented a method reversing the current list, and a method creating a new list in reversed order. The following implementation tries to correct all the above mentioned issues:public class LinkList {
int size;
Node head;
Node tail;
public LinkList() {
size = 0;
head = null;
tail = null;
}
// Bornish: if size() method is not required,
// then you can delete all code maintaining
// the "size" member data
public int size() {
return size;
}
public boolean isEmpty() {
return (head==null);
}
public void addTail(int id,String y) {
Node n1 = new Node(id,y,null);
if(head==null)
head = n1;
else
tail.setNext(n1);
tail = n1;
size++;
}
public void addHead(int id,String y) {
head = new Node(id,y,head);
if(head.getNext()==null)
tail = head;
size++;
}
public void add(int id,String y) {
// Bornish: change this to a call to addTail()
// in case you really need to add at the end
addHead(id,y);
}
public void DeleteByID(int id) {
Node n1 = head;
Node n2 = null;
Node found = null;
while (n1 != null) {
if (n1.getId()==id) {
found = n1;
n1 = null;
}
else {
n2 = n1;
n1 = n1.getNext();
}
}
if (found==null) {
System.out.println(" id missing from list ");
}
else {
if (found.getNext()==null)
tail = n2;
if (n2==null)
head = found.getNext();
else
n2.setNext(found.getNext());
size--;
}
}
public void DeleteByIndex(int x) {
Node n1 = head;
Node n2 = null;
while ( (n1 != null) && (x > 1) ) {
n2 = n1;
n1 = n1.getNext();
x--;
}
if (x!=1) {
System.out.println(" index out of boundary ");
}
else {
if (n1.getNext()==null)
tail = n2;
if (n2==null)
head = n1.getNext();
else
n2.setNext(n1.getNext());
size--;
}
}
public void ReverseMe() {
Node t = null;
Node x = null;
Node y = head;
while (y != null) {
t = y.getNext();
y.setNext(x);
x = y;
y = t;
}
tail = head;
head = x;
}
public LinkList ReversedCopyOfList() {
LinkList listNew = new LinkList();
Node n1 = head;
while (n1 != null) {
listNew.addHead(n1.getId(),n1.getValue());
n1 = n1.getNext();
}
return listNew;
}
}
/*//////////////////////////////////////////////////////////
Released into the Public Domain.
This source code is provided without warranty of any kind.
Expect bugs. Feedback would be greatly appreciated.
Feel free to use and distribute in compiled form.
Source redistribution is restricted to its unmodified form.
public void reverse()
{ if (head == null || head.next == null) return;
Object p = removeFirst();
reverse();
addLast(p);
}
Assuming you have the methods for removing the first element and removing the last element (relatively straightforward to implement).
public Object removeFirst()
{ if (head == null) throw NoSuchElementException();
Object p = head.data;
head = head.next;
return p;
}
public void addFirst(Object x)
{ Node p = new Node();
p.data = x;
// empty list
if (head == null)
head = last = p;
p.next = head;
head = p;
}
public void addLast(Object x)
{ // empty list
if (head == null)
{ addFirst(x); }
Node p = new Node();
p.data = x;
last.next = p;
last = p;
}
Reversing non-recursively:
public void reverse()
{ Node p = head;
LinkList lst = new LinkList();
while (p != null)
{ Object x = removeFirst();
lst.addFirst(x);
p = p.next;
}
this = lst;
}
(Note: I'm not sure how you have your Node class setup)
mehdi62b
October 12th, 2004, 05:02 AM
Hi there,
Take a look at my code
//C# syntax !!!
public class Node{
private object data;
private Node next;
}
public class LinkedList{
private Node first;
public Node reverse(Node first)
{
Node q=null;
Node p=first;
while(p!=null)
{
Node r=p;
p=p.next
r.next=q;
q=r
}
return q;
}
}
Bornish
October 12th, 2004, 08:58 AM
Hi mehdi62b!
Don't you think it's the same algorithm I've posted in ReverseMe() method?
And you've forgot to update first member data!
Regards,
mehdi62b
October 12th, 2004, 10:19 AM
Hi Boronish,
yes our codes are the same exactly,
can you tell me why it doesnt update first node?
I didnt get it,
Mehdi.
mehdi62b
October 13th, 2004, 05:36 AM
I didnt get why my code doesnt update first memeber,
(if it doesnt please inform me why.)
Bornish
October 13th, 2004, 10:22 AM
Isn't true that your function reverses the linked list such as "first" node becomes the last? In such case, isn't "first" member data of your list supposed to become the previous last node in the list?
I believe that the while loop is changing the "next" member of each node, thus first iteration of the loop will change "first.next = null" but "first" is never changed.
In case "first !=null", then first iteration is similar to: q=null;
p=first;
// this is the first iteration's equivalent:
{
r=first;
p=first.next;
first.next=null;
q=first;
}As you can easily see, first is never changed. Your code will work only if you call this method like this:list.first = reverse(list.first)... and that's because you are returning "q", which after the while loop is the last valid node which must become the first, since the list was just reversed.
The problem is that first is private member (as you've declared it), which means you cannot even call this reverse method, since takes as parameter the first node, but which cannot be accessed from outside this class. Then, why to declare this method as public, when only "friends" could pass the correct parameter?
Well, I'm sorry I don't fully understand you implementation... maybe I'm wrong.
Best regards,
mehdi62b
October 14th, 2004, 03:59 AM
many thanks for checking my code,
about last node in a linked list I dont suppose that it could be null,but I suppose its next node is null(according to my teacher's instructions!!! :D )
about the accessibility you were completely right and I was completely wrong,
(I could have declared them as public or like you I could have used functions or also Nested Classes)....
Best Regards.
Bornish
October 14th, 2004, 04:18 AM
Well, just read a post here about friend in C++ and internal in C#, from where I've learned something about the less granularity in C#, so, nested classes might be good solution, since lists & nodes are used together,... but we can hope we don't need nodes in other classes, because that will mean re-declaring the class node (i think)... don't have too much experience in C#, yet :)
About the first member data of a class list, as you've declare it... after calling reverse() method of a list having {1,2,3} as elements, means the list will become {3,2,1}, but are you sure that list.first will be element {3} just by calling list.reverse(list.first) ???
That was my comment about your posted code, because I don't see anything in the method's implementation that changes the member called "first".
Regards,
mehdi62b
October 14th, 2004, 06:23 AM
but we can hope we don't need nodes in other classes,but suppose we want to use our nodes in other kinds of Linked Lists,suppose we have two kinds of Linked List (like singly and doubly)....
so I think its better we dont use Nested Classes,
about the reversing the linked list
suppose my linke List was
Node1-->Node2-->Node3-->null(Node1 is the first node and Node3 is last one)
now I call Node result=list.reverse(Node1);
my linkedlist changes to this,
null<--Node1<--Node2<--Node3
and that method returns me Node3 as first Node of reversed LinkedList
(result would be Node3 as the first node in reversed Linked List)
Bornish
October 14th, 2004, 07:22 AM
Ok mehdi62b, then what's the point of keeping a member data of class LinkedList as first node in the list?
Take for example following usage of your LinkedList:LinkedList myList;
// add 10 nodes to the list:
for(int i = 0; i< 10; i++) {
myList.add(new Node(data[i]));
}
// suppose myList.first can be accessed,
// reverse entire list using your code:
Node n1 = myList.reverse(myList.first);
// at this point your list is useless
myList.first = n1;
// without above line, following will
// return null as third node:
Node third = myList.byIndex(3);
// why? because first was not updated
// after reversing the list and a search
// will start with the node pointing to
// data[0], but:
// data[9]->data[8]->data[7]->data[6]->data[5]->
// ->data[4]->data[3]->data[2]->data[1]->data[0]->null
// Thus, no third element !!!Regards,
mehdi62b
October 14th, 2004, 08:26 AM
I got!!!,
sorry for my confusion :o,
you are right,
I changed my code
//C# syntax
public class Node{
pubic object data;
public Node next;
}
public class LinkedList{
public Node first;
public static void reverse(LinkedList list)
{
Node q=null;
Node p=list.first;
while(p!=null)
{
Node r=p;
p=p.next
r.next=q;
q=r
}
list.first=q;
}
}
the underline words are changed from my previous code,
(all the fields are publuc just for simplicity ....)
I think it could work correctly :o
Bornish
October 14th, 2004, 08:31 AM
Perfect! :)
Cheers,
mehdi62b
October 14th, 2004, 10:15 AM
Cheers,
Mehdi.:)
Mutilated1
October 15th, 2004, 02:10 PM
1. There is no point in reversing a linked list, you should just traverse the list backwards instead. Pointless copying around of pointers is all you accomplish. At least that will get you a B in your programming class.
2. You should have your computers taken away for writing your own linked list classes in the first place. Use the standard template thats what they're for.
Bornish
October 16th, 2004, 01:11 AM
1. There is no point in reversing a linked list, you should just traverse the list backwards instead. Pointless copying around of pointers is all you accomplish. At least that will get you a B in your programming class.
2. You should have your computers taken away for writing your own linked list classes in the first place. Use the standard template thats what they're for.Grow up!
Luchin_plusplus
October 18th, 2004, 12:06 PM
1. There is no point in reversing a linked list, you should just traverse the list backwards instead. Pointless copying around of pointers is all you accomplish. At least that will get you a B in your programming class.
2. You should have your computers taken away for writing your own linked list classes in the first place. Use the standard template thats what they're for.
You're no reading the problem. It is a SINGLY Linked List. That means:
1.- There IS point in reversing the list. As it is a singly linked list, reversely traversing it will either require quadratic time, or linear space by the means of a stack-like positional container.
2.- Writing your own container is no wrong. As told you, he wants a singly linked list. C++ does not offer that (as standard at least). He can roll-his-own and it becomes better perfomance choice for specific problems (read about the reversing yet?). C++ STL "list" is double-linked: waste of space for single traversals and insertions.