双端链表

╰半橙微兮° 2022-07-18 01:25 163阅读 0赞

## 双端链表与传统的链表很相似，在基本链表的基础上新增一个特性：对最后一个结点的引用。如下图所示： ##

![这里写图片描述][20160904132653300]

### 与之前说到的链表相比还有一个功能是在表尾直接插入一个链结点，这样就不用普通链表一样通过遍历链表到尾部进行添加数据项了。 ###

### 双端链表的操作与单链表操作区别除了可以从头部插入数据和删除数据、查找数据以及实现关键数据项的删除等，还可以实现从链表尾部添加数据。以下是代码： ###

class Link1
    {
        public int data;
        public Link1 next;
        public Link1(int data)
        {
            this.data=data;
        }
        public void displayLink()
        {
            System.out.println("data "+data);
        }
    }

### 以上是链表节点基本信息。 ###

class FirstLastList
    {
        private Link1 firstLink=null;
        private Link1 lastLink=null;
        public void addFirst(int data)//从链表头部开始添加node
        {
            Link1 newNode=new Link1(data);
            if(firstLink==null)
            {
                lastLink=newNode;
            }
            newNode.next=firstLink;
            firstLink=newNode;
        }
        public int removeFirst()
        {
            int temp=firstLink.data;
            if(firstLink.next==null)
            {
                lastLink=null;
            }
            firstLink=firstLink.next;
            return temp;
        }
        public void showLinkList()
        {
            System.out.println("List(first--->last)");
            Link1 current=firstLink;
            while(current!=null)
            {
                current.displayLink();
                current=current.next;
            }
    
        }
    }

### 以上代码与之前的单链表区别不大，下面主要讨论一下从链表尾部加入node ###

public void addLast(int data)
        {
            Link1 newNode=new Link1(data);
            if(firstLink==null)//判断链表是否为空
            {
                firstLink=newNode;//null表明firstLink也要指向新的节点
            }
            lastLink.next=newNode;//old lastLink --->newNode
            lastLink=newNode;// newNode<---lastLink 看图理解这几个步骤
        }

### 可以用下图来描述这个从链表尾部添加数据的过程。 ###

![这里写图片描述][20160904141351757]

### 在主mian里面进行测试： ###

FirstLastList list=new FirstLastList();
            list.addFirst(1);
            list.addFirst(2);
            list.addFirst(3);
            //list.showLinkList();
            list.addLast(4);
            list.addLast(5);
            list.addLast(6);
            list.showLinkList();

### 测试结果： ###

List(first--->last)
    data 3
    data 2
    data 1
    data 4
    data 5
    data 6

### 测试remove功能与输出 ###

list.removeFirst();
            list.removeFirst();
            list.showLinkList();

List(first--->last)
    data 1
    data 4
    data 5
    data 6

### 双端链表的应用 ###

### 双端链表典型的应用就是用链表创建队列，这样可实现从链表尾部（也就是队列尾部添加数据），从链表头部删除数据（也就是队列head处删除数据）。以下创建了一个Quene类，该类使用双端链表创建队列数据结构，实质是FIFO。 ###

// 双端链表的一个重要应用是队列
    //在此基础上创建队列
    //使用链表
    class QueneBaseLink
    {
        private FirstLastList fl=null;
        public QueneBaseLink()
        {
            fl=new FirstLastList();
        }
        //对尾添加数据项
        public void addQuene(int data)
        {
            fl.addLast(data);
        }
        //队列head删除数据
        public void delete()
        {
           fl.removeFirst();
        }
        public void queneDisplay()
        {
            fl.showLinkList();
    
        }
    }

### 关于链表的效率 ###

### 在表头插入和删除速度很快，仅需要改变一两个引用值，消耗O（1）时间，平均起来查找与删除和在指定的链结点后面插入都需要搜索链表中的一半链结点，需要O（N）次比较。与数组相比，链表还是要快一些，因为插入和删除链表节点时链表不需要移动任何操作，增加效率也很显著。更多的是链表需要多少内存就使用多少内存。虽然扩展数组vector可以通过可变长改变数组长度问题，但是依然是只允许与固定大小进行增量扩展。这个解决方案在内存使用上效率还是要比链表要低一些。 ###

[20160904132653300]: /images/20220717/492bd5f83c914ab19a7c7b0d6595660e.png
[20160904141351757]: /images/20220717/4b1b1de2bddc497c9fa4be2e075b2b03.png