Reversing and Sorting my Link List

[xiiaoben]

Hi, i am quite new to c#

I have a link list and i wanna reverse the data(i have a reverse code already, but any better ways or different ways to do it??)

and sort it by (name or level or type) . some people ask me to use merge sort... but how do i do it?

How do i go about doing it

NODE CLASS

using System;

namespace DSAGAssignment
{
public class Node
{
private Entity data;
private Node link;

public Node(Entity d, Node l)
{
data = d;
link = l;
}

public Entity Data
{
get
{
return data;
}
set
{
data = value;
}
}

public Node Link
{
get
{
return link;
}
set
{
link = value;
}
}
}
}


ENTITY CLASS( this is the object to be stored in the Node)

using System;
using System.Collections.Generic;
using System.Text;

namespace DSAGAssignment
{
public class Entity
{
private String type, name;
private int level;

public Entity(String type, String name, int level)
{
this.type = type;
this.name = name;
this.level = level;
}
public String Type
{
get { return type; }
set { type = value; }
}

public String Name
{
get { return name; }
set { name = value; }
}

public int Level
{
get { return level; }
set { level = value; }
}
public override string ToString()
{
return "Type : " + type + ",\tName : " + name + ", \tLevel : " + level;
}
}
}


LINKLIST

using System;
using System.Collections.Generic;
using System.Text;

namespace DSAGAssignment
{
class LinkList
{
private Node head, tail;
private int size;

public LinkList()
{
head = null;
size = 0;
}

public Node Head
{
get { return head; }
}
public Node Tail
{
get { return tail; }
}
public int Size
{
get { return size; }
}

public void InsertFront(Entity data)
{
Node n = new Node(data, head);
if (head == null)
{
head = n;
tail = n;
}
head = n;
size++;
}

public void InsertRear(Entity data)
{
Node n = new Node(data, null);
if (head == null)
{
head = n;
tail = n;
}
else
{
tail.Link = n;
tail = n;
}
size++;
}

public bool DeleteFront()
{
if (head == null)
{
return false;
}
else
{
head = head.Link;
size--;
return true;
}
}

public bool DeleteRear()
{
if (head == null)
return false;
if (size == 1)
{
head = null;
tail = null;
size--;
return true;
}
else
{
Node cursor = head;
for (int i = 1; i < size - 1; i++)
{
cursor = cursor.Link;
}
tail = cursor;
cursor.Link = null;
size--;
return true;
}
}

public bool InsertAt(Entity data, int position)
{
Node newNode = new Node(data, null);
if (head == null)
{
head = newNode;
return true;
}
else if (position > size)
{
return false;
}
else if (position == 0 || position == 1)
{
newNode.Link = head;
head = newNode;
size++;
return true;
}
else
{
Node cursor = head;
for (int i = 1; i < position - 1; i++)
{
cursor = cursor.Link;
}
newNode.Link = cursor.Link;
cursor.Link = newNode;
size++;
return true;
}
}

public void DeleteAt(int position)
{

Node cursor = head;
if (position == 0 || position == 1)
{
head = head.Link;
}
else
{
for (int i = 1; i < position - 1; i++)
{
cursor = cursor.Link;
}
Node removedNode = cursor.Link;
cursor.Link = removedNode.Link;
removedNode.Link = null;
}
size--;
}

public bool AddUniqueEntity(string type, string name)
{
bool success = false;
if (head == null)
{
success = true;
}
for (Node cursor = head; cursor != null;cursor = cursor.Link)
{
if (cursor.Data.Type.ToString() == type && cursor.Data.Name == name)
{
success = false;
}
else
{
success = true;
}
}
return success;
}

public string DisplayByType(string type)
{
String result = "";
for (Node cursor = head; cursor != null; cursor = cursor.Link)
{
if (cursor.Data.Type.ToString() == type)
{
result += (cursor.Data.ToString() + "\n");
}
}
return result;
}

public void DeleteByType(string type)
{
Node previous = head;
if (head.Data.Type.ToString() == type)
{
head = head.Link;
size--;
}
for (Node cursor = head; cursor != null; cursor = cursor.Link)
{
if (cursor.Data.Type.ToString() == type)
{
previous.Link = cursor.Link;
size--;
}
else
previous = cursor;
}

}

public void MergeSort(LinkList list,int start_pos, int end_pos)
{
if (start_pos == end_pos)
return;

int middle_pos = (start_pos + end_pos) / 2;
MergeSort(list, start_pos, middle_pos);
MergeSort(list, middle_pos + 1, end_pos);

}

public void ReverseResult()
{
Node newHead = null;
for (Node cursor = head; cursor != null; cursor = cursor.Link)
{
if (newHead == null)
{
newHead = new Node(cursor.Data, null);
}
else
{
newHead = new Node(cursor.Data, newHead);
}
}
head = newHead;
}




public override string ToString()
{
String result = "";
int i = 0;
for (Node currentNode = head; currentNode != null; currentNode = currentNode.Link)
{
result += (i + ". " + currentNode.Data.ToString() + "\n");
i++;
}
return result;
}
}
}

[Talikag]

If I were you, I would create the class of the node and use the generic List class in System.Collections.Generic. It has built in functions, such as sorting the list, reversing it and so on...

List<myNodeClass> my_list = new List<myNodeClass>;
...

[xiiaoben]

to be frank, my school teacher provided us with the linklist code..we cant use the generic list class

[Talikag]

In this case, you'll have to implement it yourself. I would (although it might be not quite efficient) turn the list into an array, and do the operations on the array. Once I'm done with these operations, I'll turn it back to list.

That would be very convenient to sort & reverse the array, and the computer will not have to move from one adress to another in the memory (as opposed to list, array's elements appear in the memory one after another).

[xiiaoben]

can u give me some code example for sorting? base on my 3 files (linklist, node, entity)

i tried the sorting for 3 days... but cant get it to work... i tried bubble and merge sort.. but most of the example on the net shows example of sorting integer or char... i dont know how to sort my linklist

[Talikag]

As I said, turn your linklist into an array, and sort the array, and then turn the array back to linklist.
I'm sure you can figure out how to sort a simple array. There are over 30 algorithms for that.

[xiiaoben]

how do i turn my linklist into an array

[TheCPUWizard]

We do NOT *do* homework...

On the otherhand, if you post your best efforts, tell us exactly what you see in the debugger, and ask SPECIFIC questions, there will be plenty of people willing to volunteer their time to help out.

[xiiaoben]

I already said i am new to C#...


I know how to create a normal integer array and store int inside.. but i do not know how to create an array to store my linklist?

i am very new to link list.. and in Google, there are very very very few examples on linklist in c#

[TheCPUWizard]

you can ceate an array of any type..

MyType [] myar = new MyType[100];

But the whole point of a linked list is to AVOID arrays.

This is the reason for a merge sort. Keep splitting the list until you have only 1 or 2 nodes. Then you merge them back together. Never a need for arrays...

[xiiaoben]

Okay thanks.

So which sort should i use? anyone that is very easy to sort and workable its alright.