Lets start with what is a linked list:
A linked list is a data structure consisting nodes which together represent a sequence. Each node contains at least data and a reference to the next node. Hours and hours have been spent writing about linked lists, so no point on rehashing it again. For more information, you can use the google machine or check Wikepedia's page on the subject. http://en.wikipedia.org/wiki/Linked_list
Now the code
Declaring the node
Nothing fancy, straight forward thing
public class Node
{
public object data;
//recursive portion of this.
public Node next;
public Node(object data)
{
this.data = data;
}
}
Linked List
public class myLinkedList
{
public Node head;
Node current;
public void Add(Node n)
{
//self explanatory, but just in case
// if the top has not been initialized, then do it
if (head == null)
{
head = n;
current = n;
}
else
{
//if there something there, then just add the new
// node to the end, notice you first set the next property,
// then set current
current.next = n;
current = current.next;
}
}
public void InsertAtTop(Node n)
{
current = head;
//check to make sure there is something
// there
if (n == null) { return; }
n.next = current;
head = n;
}
public void Insert(Node n)
{
//check to make sure there is something
// there
if (n == null) { return; }
//this operation would check if where should I add a value on the list.
current = head;
//check the first element..
if ((int)current.data >= (int)n.data)
{
n.next = current;
head = n;
return;
}
//if the first element was ok, then move to the rest
current = current.next;
while (current != null)
{
if ((int)current.data <= (int)n.data)
{
n.next = current.next;
current.next = n;
return;
}
current = current.next;
}
//now if I got here then this should be the last item on the list
current.next = n;
}
public string ReverseAndParse()
{
string temp = "";
current = head;
while (current.next != null)
{
temp = string.Concat(current.data.ToString(), temp);
current = current.next;
}
//add the last item...
temp = string.Concat(current.data.ToString(), temp);
return temp;
}
public string Parse()
{
string temp = "";
current = head;
while (current.next != null)
{
temp = string.Concat(temp, current.data.ToString());
current = current.next;
}
//add the last item...
temp = string.Concat(temp, current.data.ToString());
return temp;
}
public void DisplayItems()
{
Node n = head;
while (n.next != null)
{
Console.WriteLine("Node : {0}", n.data);
n = n.next;
}
//display the lastone
Console.WriteLine("Node : {0}", n.data);
}
public void RemoveDuplicates()
{
current = head;
while (current.next != null)
{
Node n = current;
while (n.next != null)
{
if (n.next.data.Equals(current.data))
{
n.next = n.next.next;
}
else
{
n = n.next;
}
}
current = current.next;
}
}
public Node Split(object x, Node node)
{
Node ihead = node;
Node tail = node;
while (node.next != null)
{
Node next = node.next;
if ((int)node.data < (int)x)
{
node.next = ihead;
ihead = node;
}
else
{
tail.next = node;
tail = node;
}
node = next;
}
//we need the last record
if ((int)node.data < (int)x)
{
node.next = ihead;
ihead = node;
}
else
{
tail.next = node;
tail = node;
}
tail.next = null;
// bottom.next = top;
this.head = ihead;
return ihead;
}
public Node addNodes(Node first, Node second, int CarryOver)
{
Node n = new Node(CarryOver);
int value = (int)(first == null ? 0 : (int)first.data) + (second == null ? 0 : (int)second.data) + CarryOver;
n.data = (value >= 10 ? (value - 10) : value);
if (first != null || second != null)
{
Node New = (addNodes((first.next == null ? null : first.next), (second.next == null ? null : second.next), (value / 10)));
if (New != null)
{
Add(New);
}
}
return n;
}
public Node BreakAndFix()
{
current = head;
// Node breaker = new Node(current.next.next.data);
Node breaker = current.next.next;
while (current.next != null)
{
current = current.next;
}
//break it here
current.next = head.next.next;
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null)
{
slow = slow.next;
fast = fast.next.next;
if (slow.Equals(fast))
{
break;
}
}
if (fast == null || fast.next == null)
{
return null;
}
slow = head;
while (slow != fast)
{
slow = slow.next;
fast = fast.next;
}
return fast;
}
}
No comments:
Post a Comment