Basic Data Structure: Linked Lists

Basic Data Structures: Linked Lists

In a return to basics – and plenty of nothing to do – I implemented my own little linked list. Given the state of modern computing I have never really needed to implement a linked list, .Net framework has excellent libraries that manage lists and arrays, however, I guess it is always useful to understand the algorithms and foundations of computer science.

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 Wikipedia’s page on the subject. http://en.wikipedia.org/wiki/Linked_list
LinkedList

Now the code

Declaring the node

Nothing fancy, straight forward thing
 public class Node
    {
        public object data;       
        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)
        {
           
            if (head == null)
            {
                head = n;
                current = n;
            }
            else
            {
               current.next = n;
                current = current.next;
            }
        }
        public void InsertAtTop(Node n)
        {
            current = head;
            if (n == null)
              {
                    return;
               }
            n.next = current;
            head = n;
        }
        public void Insert(Node n)
        {
            if (n == null) { return; }
            
            if ((int)current.data >= (int)n.data)
            {
                n.next = current;
                head = n;
                return;
            }
            current = current.next;
            while (current != null)
            {
                if ((int)current.data <= (int)n.data)
                {
                    n.next = current.next;
                    current.next = n;
                    return;
                }
                current = current.next;
            }
            current.next = n;
        }
        public string ReverseAndParse()
        {
            string temp = “”;
            current = head;
            while (current.next != null)
            {
                temp = string.Concat(current.data.ToString(), temp);
                current = current.next;
            }
            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;
            }
            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;
            }
           
            if ((int)node.data < (int)x)
            {
                node.next = ihead;
                ihead = node;
            }
            else
            {
                tail.next = node;
                tail = node;
            }
            tail.next = null;
           
            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 = current.next.next;
            while (current.next != null)
            {
                current = current.next;
            }         
            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;
        }
    }

One thought on “Basic Data Structure: Linked Lists

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s