The realization of one-way linked list C -- understanding the construction of data structure with object-oriented thinking

  1. Why use one-way linked list?      

First of all, the deletion of one-way linked list is very convenient. If you need to delete data frequently in your program design, it is a good choice to use one-way linked list as data structure. The delete operation of linked list only needs to delete the data at the location to be deleted, and does not need to shift the elements behind the location one by one, which greatly improves the efficiency of the delete operation. The insert operation is the same, because of the non sequential and non continuous storage structure, the complexity of the insertion of linked list is O(1), only a node needs to be created to modify the pointer relationship at the location, while the array structure is complex At the same time, if the capacity of the array reaches a limit, the capacity expansion will be triggered.

However, although the deletion and insertion of linked list are more efficient than that of digital structure, the cost of indexing the data on a linked list is greater than that of array structure. The former is the complexity of O (log n), and the latter is only O(1). When we design programs, we need to create them according to our own needs. There is no perfect thing in the world.

2. Code implementation of one-way linked list (C ×)

Analysis

                                 

Unlike arrays, linked lists need continuous memory addresses, and the memory addresses of each element in the linked list can be distributed. Unordered, it needs to store an additional variable in each data to point to its next data address: next, to get each element in the linked list.

We call this data structure composed of data and next as a "node", which has two basic fields.

Next, start to construct the properties and behaviors of the linked list.

A linked list has header information Head, which represents the information Length and other attributes of its own Length;

The behaviors of linked list include index element, adding element at the end, inserting element at any position, deleting element at specified position, obtaining element at a certain position, calculating element's position in the table, etc.

// This is the parent class of a single data node in the linked list. T is the parameter used to determine the data type. The fixed writing format of the class
public class LoopLinkNode<T> where T : object
{
    private T data;// The data domain of the node,
    private LoopLinkNode<T> next; // Next node of this node (pointer field)

    public T Data 
    {
        set { data = value; }
        get { return data; }
    }
    public LoopLinkNode<T> Next
    {
        set { next = value; }
        get { return next; }
    }

    // Constructors, creating nodes
    public LoopLinkNode(T data)
    {
        this.data = data;
        next = null;
    }
}
    // This is the parent class of the linked list. The properties, fields and behaviors of the linked list are defined here
    public class LoopLink<T> where T : object
    {
        // The constructor of the linked list is called at the time of new. Here, an empty linked list is created, and the head node is empty
        public LoopLink()
        {
            this.head = null;            
        }

        // Header information property of linked list
        private LoopLinkNode<T> head;
        public LoopLinkNode<T> Head
        {
            set
            {
                head = value;
                head.Next = head;
            }
            get { return head; }
        }

        // Length attribute of linked list
        public int Length { get { return GetLength(); } }

        /// <summary>
        //Indexer
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public LoopLinkNode<T> this[int index]
        {
            set
            {
                if (IsEmpty())
                    throw new Exception("Linked list is empty.");
                if (index < 0 || index > this.Length - 1)
                    throw new Exception("Index exceeds linked list length");
                LoopLinkNode<T> node = head;
                for (int i = 0; i < index; i++)
                {
                    node = node.Next;                    
                }
                node.Data = value.Data;
                node.Next = value.Next;
            }
            get
            {
                if (IsEmpty())
                    throw new Exception("Linked list is empty.");
                if (index < 0 || index > this.Length - 1)
                    throw new Exception("Index exceeds linked list length");
                LoopLinkNode<T> node = head;
                for (int i = 0; i < index; i++)
                {
                    node = node.Next;                    
                }
                return node;
            }
        }

        /// <summary>
        ///Get link length
        /// </summary>
        /// <returns></returns>
        public int GetLength()
        {
            if (IsEmpty())
                return 0;
            int length = 1;
            LoopLinkNode<T> temp = head;
            while (temp.Next != head)
            {
                temp = temp.Next;
                length++;
            }
            return length;
        }

        /// <summary>
        ///Clear all elements of the list, just leave the header information blank
        /// </summary>
        public void Clear()
        {
            this.head = null;
        }

        /// <summary>
        ///Check if the list is empty
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {
            if (head == null)
                return true;
            return false;
        }

        /// <summary>
        ///Check if the list is full
        /// </summary>
        /// <returns></returns>
        public bool IsFull()
        {
            return false;
        }

        /// <summary>
        ///Add a new item at the end of the list
        /// </summary>
        /// <param name="item"></param>
        public void Append(T item)
        {
            if (IsEmpty())
            {
                this.Head = new LoopLinkNode<T>(item);
                return;
            }
            LoopLinkNode<T> node = new LoopLinkNode<T>(item);
            LoopLinkNode<T> temp = head;
            while (temp.Next != head)
            {
                temp = temp.Next;
            }
            temp.Next = node;
            node.Next = head;
        }

        /// <summary>
        ///Add a new item at the specified location of the linked list
        /// </summary>
        /// <param name="item"></param>
        /// <param name="index"></param>
        public void Insert(T item, int index)
        {
            if (IsEmpty())
                throw new Exception("Data link list is empty");
            if (index < 0 || index > this.Length)
                throw new Exception("Given index exceeds linked list length");
            LoopLinkNode<T> temp = new LoopLinkNode<T>(item);
            LoopLinkNode<T> node = head;
            if (index == 0)
            {
                while (node.Next != head)
                {
                    node = node.Next;
                }
                node.Next = temp;
                temp.Next = this.head;
                return;
            }
            for (int i = 0; i < index - 1; i++)
            {
                node = node.Next;
            }
            LoopLinkNode<T> temp2 = node.Next;
            node.Next = temp;
            temp.Next = temp2;
        }

        /// <summary>
        ///Delete the item at the specified location of the linked list
        /// </summary>
        /// <param name="index"></param>
        public void Delete(int index)
        {
            if (IsEmpty())
                throw new Exception("The list is empty. There are no items to clear");
            if (index < 0 || index > this.Length - 1)
                throw new Exception("Given index exceeds linked list length");
            LoopLinkNode<T> node = head;
            if (index == 0)
            {
                while (node.Next != head)
                {
                    node = node.Next;
                }
                this.head = head.Next;
                node.Next = this.head;
                return;
            }
            for (int i = 0; i < index - 1; i++)
            {
                node = node.Next;
            }
            node.Next = node.Next.Next;
        }

        /// <summary>
        ///Gets the value of the element at the specified location of the linked list
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public T GetItem(int index)
        {
            if (index < 0 || index > this.Length - 1)
                throw new Exception("Index exceeds linked list length");
            LoopLinkNode<T> node = head;
            for (int i = 0; i < index; i++)
            {
                node = node.Next;
            }
            return node.Data;
        }

        /// <summary>
        ///Find out which element in the linked list is this value according to the given value. If there are two elements with the same value in the linked list, take the element in front of the linked list
        /// </summary>
        /// <param name="value"></param>
        /// <returns></returns>
        public int Locate(T value)
        {
            if (IsEmpty())
                throw new Exception("Linked list is empty.");
            LoopLinkNode<T> node = head;
            int index = 0;
            while (node.Next != head)
            {
                if (node.Data.Equals(value))
                    return index;
                else
                    index++;
                node = node.Next;
            }
            if (node.Data.Equals(value))
                return index;
            else
                return -1;
        }
}

Test code:

    private void Start()
    {
        LoopLink<Vector2> linkList = new LoopLink<Vector2>();
        for (int i = 0; i < 10; i++)
        {
            linkList.Append(new Vector2(i, i % 2));
        }
        Debug.Log("raw data:");
        for (int i = 0; i < linkList.Length; i++)
        {
            Debug.Log(linkList[i].Data);
        }
        Debug.Log("Insert the element in the second to last position (999, 999) Later:");
        linkList.Insert(new Vector2(999, 999), linkList.Length - 2);
        for (int i = 0; i < linkList.Length; i++)
        {
            Debug.Log(linkList[i].Data);
        }
        linkList.Delete(linkList.Length - 1);
        Debug.Log("Delete the last element:");
        for (int i = 0; i < linkList.Length; i++)
        {
            Debug.Log(linkList[i].Data);
        }
        Debug.Log("Take out the second element: " + linkList.GetItem(1));
        Debug.Log("(0,0)The index of the element in the linked list is:" + linkList.Locate(Vector2.zero));
    }

Test results:

                                                        

 

Published 5 original articles, won praise 1, and visited 267
Private letter follow

Tags: Attribute

Posted on Thu, 13 Feb 2020 03:32:48 -0800 by Operandi