【数据结构】带头结点的链表实现

MaybeHC

发布于 2024-04-23 19:06:11

840

发布于 2024-04-23 19:06:11

上次写了简单的链表实现，这次完善了链表的功能并添加了头结点。

实现

class LinkedList<E>
    {
        private class Node
        {
            public E e;
            public Node next;
            public Node(E e,Node next)
            {
                this.e = e;
                this.next = next;
            }
            public Node(E e) : this(e, null)
            {

            }
            public Node() : this(default(E), null)
            {

            }
            public override string ToString()
            {
                return e.ToString();
            }
        }
        private Node dummyhead;
        private int size;
        public LinkedList()
        {
            dummyhead = new Node(default(E),null);
            size = 0;
        }
        public int getSize()
        {
            return size;
        }
        public bool isEmpty()
        {
            return size == 0;
        }
        //在链表头添加新的元素e
        public void addFirst(E e)
        {
            add(0, e);           
        }
        //在链表的index位置添加新的元素e
        public void add(int index,E e)
        {
            if (index < 0 || index > size)
                throw new ArgumentException("Add failed. Illegal index.");

                //找到索引位置的前一元素
                Node prev = dummyhead;
                for (int i = 0; i < index; i++)
                    prev = prev.next;
                Node node = new Node(e);
                node.next = prev.next;
                prev.next = node;

                //prev.next = new Node(e, prev.next);
                size++;
            
        }
        //在链表末尾添加新的元素e
        public void addLast(E e)
        {
            add(size, e);
        }
        //获得链表的第index个位置的元素
        public E get(int index)
        {
            if (index < 0 || index >= size)
                throw new ArgumentException("Get failed.Illegal index.");
            Node cur = dummyhead.next;
            for (int i = 0; i < index; i++)
                cur = cur.next;
            return cur.e;
        }
        //获得链表的第一个元素
        public E getFirst()
        {
            return get(0);
        }
        //获得链表的最后一个元素
        public E getLast()
        {
            return get(size - 1);
        }
        //修改链表的index位置的元素e
        public void set(int index ,E e)
        {
            if (index < 0 || index >= size)
                throw new ArgumentException("Set failed.Illegal index.");
            Node cur = dummyhead.next;
            for (int i = 0; i < index; i++)
                cur = cur.next;
            cur.e = e;
        }
        //查找链表中是否存在元素e
        public bool contains(E e)
        {
            Node cur = dummyhead.next;
            while (cur != null)
            {
                if (cur.e.Equals(e)) return true;
                cur = cur.next;
            }
            return false;
        }
        //从链表中删除指定位置的元素
        public E remove(int index)
        {
            if (index < 0 || index >= size)
                throw new ArgumentException("Remove failed.Illegal index.");
            Node prev = dummyhead;
            for (int i = 0; i < index; i++)
                prev = prev.next;
            Node retNode = prev.next;
            prev.next = retNode.next;
            retNode.next = null;
            size--;
            return retNode.e;
        }
        //从链表中给删除第一个元素，返回删除的元素
        public E removeFirst()
        {
            return remove(0);
        }
        public E removeLast()
        {
            return remove(size - 1);
        }
        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            Node cur = dummyhead.next;
            while (cur != null)
            {
                sb.Append(cur + "->");
                cur = cur.next;
            }
            sb.Append("NULL");
            return sb.ToString();
        }
    }

写个测试类测试一下

测试

static void Main(string[] args)
        {
            LinkedList<int> linkedList = new LinkedList<int>(); 
            for(int i = 0; i < 5; i++)
            {
                linkedList.addFirst(i);
                Console.WriteLine(linkedList);
            }
            linkedList.add(2, 666);
            Console.WriteLine(linkedList);
            linkedList.remove(2);
            Console.WriteLine(linkedList);
            linkedList.removeFirst();
            Console.WriteLine(linkedList);
            linkedList.removeLast();
            Console.WriteLine(linkedList);
            Console.ReadKey();
        }