精华内容
下载资源
问答
  • Java语言中链表和双向链表链表是一种重要的数据结构,在程序设计中占有很重要的地位。C语言和C++语言中是用指针来实现链表结构的,由于Java语言不提供指针,所以有人认为在Java语言中不能实现链表,其实不然,Java...

    Java语言中链表和双向链表

    链表是一种重要的数据结构,在程序设计中占有很重要的地位。C语言和C++语言中是用指针来实现链表结构的,由于Java语言不提供指针,所以有人认为在Java语言中不能实现链表,其实不然,Java语言比C和C++更容易实现链表结构。Java语言中的对象引用实际上是一个指针(本文中的指针均为概念上的意义,而非语言提供的数据类型),所以我们可以编写这样的类来实现链表中的结点。

    class Node

    {

    Object data;

    Node next;//指向下一个结点

    }

    将数据域定义成Object类是因为Object类是广义超类,任何类对象都可以给其赋值,增加了代码的通用性。为了使链表可以被访问还需要定义一个表头,表头必须包含指向第一个结点的指针和指向当前结点的指针。为了便于在链表尾部增加结点,还可以增加一指向链表尾部的指针,另外还可以用一个域来表示链表的大小,当调用者想得到链表的大小时,不必遍历整个链表。下图是这种链表的示意图:

    链表的数据结构

    我们可以用类List来实现链表结构,用变量Head、Tail、Length、Pointer来实现表头。存储当前结点的指针时有一定的技巧,Pointer并非存储指向当前结点的指针,而是存储指向它的前趋结点的指针,当其值为null时表示当前结点是第一个结点。那么为什么要这样做呢?这是因为当删除当前结点后仍需保证剩下的结点构成链表,如果Pointer指向当前结点,则会给操作带来很大困难。那么如何得到当前结点呢,我们定义了一个方法cursor(),返回值是指向当前结点的指针。类List还定义了一些方法来实现对链表的基本操作,通过运用这些基本操作我们可以对链表进行各种操作。例如reset()方法使第一个结点成为当前结点。insert(Object d)方法在当前结点前插入一个结点,并使其成为当前结点。remove()方法删除当前结点同时返回其内容,并使其后继结点成为当前结点,如果删除的是最后一个结点,则第一个结点变为当前结点。

    链表类List的源代码如下:

    import java.io.*;

    public class List

    {

    /*用变量来实现表头*/

    private Node Head=null;

    private Node Tail=null;

    private Node Pointer=null;

    private int Length=0;

    public void deleteAll()

    /*清空整个链表*/

    {

    Head=null;

    Tail=null;

    Pointer=null;

    Length=0;

    }

    public void reset()

    /*链表复位,使第一个结点成为当前结点*/

    {

    Pointer=null;

    }

    public boolean isEmpty()

    /*判断链表是否为空*/

    {

    return(Length==0);

    }

    public boolean isEnd()

    /*判断当前结点是否为最后一个结点*/

    {

    if(Length==0)

    throw new java.lang.NullPointerException();

    else if(Length==1)

    return true;

    else

    return(cursor()==Tail);

    }

    public Object nextNode()

    /*返回当前结点的下一个结点的值,并使其成为当前结点*/

    {

    if(Length==1)

    throw new java.util.NoSuchElementException();

    else if(Length==0)

    throw new java.lang.NullPointerException();

    else

    {

    Node temp=cursor();

    Pointer=temp;

    if(temp!=Tail)

    return(temp.next.data);

    else

    throw new java.util.NoSuchElementException();

    }

    }

    public Object currentNode()

    /*返回当前结点的值*/

    {

    Node temp=cursor();

    return temp.data;

    }

    public void insert(Object d)

    /*在当前结点前插入一个结点,并使其成为当前结点*/

    {

    Node e=new Node(d);

    if(Length==0)

    {

    Tail=e;

    Head=e;

    }

    else

    {

    Node temp=cursor();

    e.next=temp;

    if(Pointer==null)

    Head=e;

    else

    Pointer.next=e;

    }

    Length++;

    }

    public int size()

    /*返回链表的大小*/

    {

    return (Length);

    }

    public Object remove()

    /*将当前结点移出链表,下一个结点成为当前结点,如果移出的结点是最后一个结点,则第一个结点成为当前结点*/

    {

    Object temp;

    if(Length==0)

    throw new java.util.NoSuchElementException();

    else if(Length==1)

    {

    temp=Head.data;

    deleteAll();

    }

    else

    {

    Node cur=cursor();

    temp=cur.data;

    if(cur==Head)

    Head=cur.next;

    else if(cur==Tail)

    {

    Pointer.next=null;

    Tail=Pointer;

    reset();

    }

    else

    Pointer.next=cur.next;

    Length--;

    }

    return temp;

    }

    private Node cursor()

    /*返回当前结点的指针*/

    {

    if(Head==null)

    throw new java.lang.NullPointerException();

    else if(Pointer==null)

    return Head;

    else

    return Pointer.next;

    }

    public static void main(String[] args)

    /*链表的简单应用举例*/

    {

    List a=new List ();

    for(int i=1;i<=10;i++)

    a.insert(new Integer(i));

    System.out.println(a.currentNode());

    while(!a.isEnd())

    System.out.println(a.nextNode());

    a.reset();

    while(!a.isEnd())

    {

    a.remove();

    }

    a.remove();

    a.reset();

    if(a.isEmpty())

    System.out.println("There is no Node in List \n");

    System.in.println("You can press return to quit\n");

    try

    {

    System.in.read();

    //确保用户看清程序运行结果

    }

    catch(IOException e)

    {}

    }

    }

    class Node

    /*构成链表的结点定义*/

    {

    Object data;

    Node next;

    Node(Object d)

    {

    data=d;

    next=null;

    }

    }

    读者还可以根据实际需要定义新的方法来对链表进行操作。双向链表可以用类似的方法实现只是结点的类增加了一个指向前趋结点的指针。

    可以用这样的代码来实现:

    class Node

    {

    Object data;

    Node next;

    Node previous;

    Node(Object d)

    {

    data=d;

    next=null;

    previous=null;

    }

    }

    当然,双向链表基本操作的实现略有不同。链表和双向链表的实现方法,也可以用在堆栈和队列的实现中,这里就不再多写了,有兴趣的读者可以将List类的代码稍加改动即可。

    展开全文
  • C语言实现链表之双向链表(十二)判断链表是否为空和获取链表长度  上一篇文章给出了设置结点数据与获取结点数据的两个函数,本篇文章将给出判断链表是否为空和获取链表长度的函数,共两个函数。 /*==========...

    C语言实现链表之双向链表(十二)判断链表是否为空和获取链表长度


        上一篇文章给出了设置结点数据与获取结点数据的两个函数,本篇文章将给出判断链表是否为空和获取链表长度的函数,共两个函数。

    /*============================================================================== 
    *   操作  :检查链表是否为空
    *   操作前:pHeadNode为链表的头指针
    *   操作后:如果链表为空,则返回TRUE,否则返回FALSE
    ==============================================================================*/
    C_Bool CheckMyListEmpty(MyListNode* pHeadNode)
    {
        if(pHeadNode == NULL)
        {
            printf("The list is empty.\n");
            return TRUE;
        }
        else
        {
            printf("The list is no empty.\n");
            return FALSE;
        }
    }
    
    /*============================================================================== 
    *   操作  :获得链表的长度
    *   操作前:pHeadNode为链表的头指针
    *   操作后:返回链表的长度
    ==============================================================================*/
    int GetMyListLen(MyListNode* pHeadNode)
    {
        MyListNode* pListNodeTmp = pHeadNode;
        int iLen = 0;
    
        // 判断是否有链表输入
        if(pHeadNode == NULL)
        {
            fprintf(stderr, "There is no list.\n");
            return -1;
        }
    
        // 获得长度
        while(pListNodeTmp != NULL)
        {
            iLen++;
            pListNodeTmp = pListNodeTmp->pNextNodeAddr;
        }
        return iLen;
    }

        这两个函数比较简单,对于常见的错误处理以及布尔变量此处不再过多去说,大家一看便知。
    展开全文
  • Python数据结构与算法:第3-9课时:双向链表及添加元素、判断链表是否为空 双向链表 后继节点,某个节点,前驱节点。 例子: 比如40这个节点的前驱节点就是100, 后继节点就是6 定义: 一种更复杂的链表是...

    Python数据结构与算法:第3-9课时:双向链表及添加元素、判断链表是否为空



    双向链表

    在这里插入图片描述
    在这里插入图片描述
    后继节点,某个节点,前驱节点。



    例子:

    比如40这个节点的前驱节点就是100, 后继节点就是6
    在这里插入图片描述



    定义:

    一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接:一个指向前一个节点,当此节点为第一个节点时,指向空值;而另一个指向下一个节点,当此节点为最后一个节点时,指向空值。


    所需要的一些操作:

    • is_empty() 链表是否为空
    • length() 链表长度
    • travel() 遍历链表
    • add(item) 链表头部添加
    • append(item) 链表尾部添加
    • insert(pos, item) 指定位置添加
    • remove(item) 删除节点
    • search(item) 查找节点是否存在


    实现

    节点的代码:

    class Node(object):
        """双向链表节点"""
        def __init__(self, item):
            self.item = item
            self.next = None
            self.prev = None
    

    self.next 为后继节点的地址,
    prev 为前继节点的地址。



    双链列表定义的代码:

    只需要顶一个函数头就可以了,和单链列表一样。

    class DLinkList(object):
        """双向链表"""
        def __init__(self,node = None):
            self._head = node
    


    判断链表是否为空:

    def is_empty(self):
        """判断链表是否为空"""
        return self._head == None
    

    与单向链表一样。



    判断双向链表的长度:

    与单向链表一样:

    只需要从头遍历到尾就可以实现了。

    def length(self):
        """返回链表的长度"""
        cur = self._head
        count = 0
        while cur != None:
            count += 1
            cur = cur.next
        return count
    


    遍历双向链表的长度:

    也与单链列表一致:

    def travel(self):
        """遍历链表"""
        cur = self._head
        while cur != None:
            print(cur.item)
            cur = cur.next
    


    在头部插入一个节点 add:

    在这里插入图片描述
    让 之前表头self._head指向 新节点node地址。

    实现代码:

    def add(self, item):
        """头部插入元素"""
        node = Node(item)
        if self.is_empty():
            # 如果是空链表,将_head指向node
            self._head = node
        else:
            # 将node的next指向_head的头节点
            node.next = self._head
            # 将_head的头节点的prev指向node
            self._head.prev = node
            # 将_head 指向node
            self._head = node
    


    在双向链表尾部添加元素:

    实现代码:

    def append(self, item):
        """尾部插入元素"""
        node = Node(item)
        if self.is_empty():
            # 如果是空链表,将_head指向node
            self._head = node
        else:
            # 移动到链表尾部
            cur = self._head
            while cur.next != None:
                cur = cur.next
            # 将尾节点cur的next指向node
            cur.next = node
            # 将node的prev指向cur
            node.prev = cur
    


    在双向链表尾指定位置插入元素:

    有数双向链表将节点的头尾均连起来,所以只需要一个游标就可以实现了。

    实现代码:

    def insert(self, pos, item):
        """在指定位置添加节点"""
        if pos <= 0:
            self.add(item)
        elif pos > (self.length()-1):
            self.append(item)
        else:
            node = Node(item)
            cur = self._head
            count = 0
            # 移动到指定位置的前一个位置
            while count < (pos-1):
                count += 1
                cur = cur.next
            # 将node的prev指向cur
            node.next = cur
            # 将node的next指向cur的下一个节点
            node.prev = cur.prev
            # 将cur的下一个节点的prev指向node
            cur.prev.next = node
            # 将cur的next指向node
            cur.prev = node
    
    展开全文
  • 一、循环链表 循环链表是一种头尾相接的链表(即:中最后一个结点的指针域指向头结点,整个链表形成一个环) ...next是否为空,而是判断他们是否等于头指针 循环条件 p!=NULL → p!=L p->next!=NULL → p-&

    一、循环链表

    • 循环链表是一种头尾相接的链表(即:表中最后一个结点的指针域指向头结点,整个链表形成一个环)

    • 优点:从表中任一结点出发均可找到表中其他结点

    • 注意:由于循环链表中没有NULL指针,故涉及遍历操作时,其终止条件就不再像非循环链表那样判断p或p->next是否为空,而是判断他们是否等于头指针

    • 循环条件

      p!=NULL → p!=L

      p->next!=NULL → p->next!=L

      ​ 单链表 单循环链表

    • 带尾指针循环链表的合并

    LinkList Connect(LinkList Ta,LinkList Tb)
    {
        p=Ta->next;
        Ta->next=Tb->next->next;
        delete Tb->next;
        Tb->next=p;
        return Tb;
    }
    

    二、双向链表

    • 双向链表:在单链表的每个结点里再增加一个指向其前驱的指针域prior,这样链表中就形成了有两个方向不同的链,故称为双向链表

    • 双向循环链表:和单链的循环表类似,双向链表也可以有循环表

      • 让头结点的前驱指针指向链表的最后一个结点
      • 让最后一个结点的后继指针指向头结点
    • 双向链表结构的对称性:

      p->prior->next = p = p->next->prior

    三、双向链表的插入

    void ListInsert_DuL(DuLinkList &L,int i,ElemTyoe e)
    {
        if(!(p=GetElemP_DuL(L,i)))
            return ERROR;
        s=new DuLNode;
        s->date=e;
        s->prior=p->prior;
        p->prior->next=s;
        s->next=p;
        p->prior=s;
        return OK;
    }
    

    四、双向链表的删除

    void ListDelete_DuL(DuLink &L,int i,ElemType &e)
    {
        if(!(p=GetElemP_DuL(L,i)))
            return ERROR;
        e=p->data;
        p->prior->next=p->next;
        p->next->prior=p->prior;
        free(p);
        return OK;
    }
    
    展开全文
  • 循环链表,双向链表

    2017-10-10 19:13:37
    循环链表与顺序链表之间的区别:循环链表最后一个数据的next指针域不为空,而是指向头结点,其他基本操作大体相同,只是在判断表结束的条件变为判断节点的引用域是否为头引用 双向链表 /** * @author NeoSong ...
  • 双端链表和双向链表

    2020-01-27 00:39:59
    如果链表为空,则直接设置头节点为新增节点,否则设置尾节点的后一个节点为新增节点 4.从头部删除节点 判断头节点是否指向下一个节点,如果没有则设置节点为null 1.创建双端链表节点Node //头节点 public class ...
  • 文章目录双向链表构建双向链表判断链表是否为空(与单链表同)链表长度遍历添加元素:头插法添加元素:尾插法添加元素:指定位置删除节点查找节点是否存在单向循环链表构建单向循环链表判断链表是否为空链表长度遍历...
  • 用Java定义一个双向链表,实现链表的基本操作: 初始化、获取头结点、添加新元素、删除链表元素、 获取链表元素、查找链表元素、更新链表中某个元素、 判断链表是否为空、求链表元素个数、输出链表元素、清空链表。...
  • 使用带 head 头的双向链表实现 文章目录单向链表与双向链表对比:双向链表的遍历,添加,修改与删除:1、遍历2、添加3、修改4、删除 单向链表与双向链表对比: ... // 判断链表是否为空 if (head.next =.
  • 双向链表

    2015-01-11 13:50:18
    双向链表 定义:在单链表的每个结点里再增加一个指向其直接前驱的指针域prior。...3 判断链表是否为空 4 计算链表长度 5 向链表插入节点 6 从链表删除节点 typedef int ElemType; typedef struct LNode{ ElemType
  • 1.循环链表:首尾相连的链表。 2.单循环链表:在单链表中,如果最后一个结点的链域值不是NULL,而是指向头结点,则...5.判断双向循环链表为空的条件:头结点的前驱和后继指针均指向了自己。 6.算法package com.bocl
  • 循环链表/双向链表

    2018-10-17 23:09:07
    is_empty() 判断链表是否为空 length() 返回链表的长度 travel() 遍历 add(item) 在头部添加一个节点 append(item) 在尾部添加一个节点 insert(pos, item) 在指定位置pos添加节点 remove(item) 删除...
  • 单向链表 class Node: def __init__(self,var): self.var = var self.next = None class SingleLinkList: def __init__(self,node=None... # 判断链表是否为空 def is_empty(self): return self.__head == None
  • Java实现双向链表

    2020-03-22 23:22:42
    用Java定义一个双向链表,实现链表的基本操作: 初始化、获取头结点、添加新元素、删除链表元素、 获取链表元素、查找链表元素、更新链表中某个元素、 判断链表是否为空、求链表元素个数、输出链表元素、清空链表。
  • 数据结构之循环链表和双向链表 1.循环链表 循环链表是另一种形式的链式存储结构,其特点是单链表的最后一个结点的指针不为空,而是指向头结点(带头结点的链表)或第一个结点(不带头结点的链表),整个链表形成...
  • 如果链表为空,则直接设置头结点为新添加的节点,否则设置尾节点的后一个节点为新添加节点。 四、从头部进行删除 判断头结点是否为下一个结点,如果没有则设置为结点为null。 双端链表的好处就是可以从尾结点进行...
  • 从尾部进行插入时,如果链表为空,则直接设置头节点为新添加的节点,否则设置尾节点的后一个结点为新添加节点。 从头部进行删除时,判断头节点是否有下一个节点,如果没有则设置尾节点为...
  • 单链表和循环链表的唯一区别就是尾结点的指针值,所以循环判断时,由原来的是否为空,现在则是是否为头结点,则循环结束。 1.2.2 实现 与单链表实现类似,修改循环判断条件即可。可参考:https://www.cnb...
  • 循环链表双向链表

    2016-04-19 22:16:52
    其实循环链表和单链表的主要差异在于循环的判断条件上,原来是判断p->next是否为空,现在则是判断p->next是否等于头结点,则表示循环结束 改造单链表,不用头指针,而是用指向终端结点的尾指针来表示循环链表,此时...
  • 循环链表 将单链表中终端结点的指针...使空链表与非空链表处理一致,通常设置一个头结点。 [并非必须设置头结点] 对于非空的循环链表如下图: 循环链表和单链表的主要差异就在于循环的条件判断上,原来是 ...
  • 与单链表区别,原来判断p->next是否为空,现在判断p->next不等于头结点则循环结束不用头指针,使用指向终端节点的尾指针表示循环链表 将两个循环链表合并成一个:p=rearA->next;//保存A头结点 rearA->next = ...
  • 文章目录循环链表单循环链表定义初始化操作插入操作删除操作返回节点所在位置约瑟夫问题 循环链表 对于单链表,由于每个结点只储存了向后的指针,到了尾部标识就...循环链表的单链表的主要差距就在于循环的判断空链表
  • 双向链表的删除操作

    万次阅读 2021-03-19 19:32:50
    //从双向链表中删除一个节点 //说明 //1.对于双向链表,我们可以直接找到删除的这个节点 //2.... public void del(int no) { ... System.out.println("链表为空,无法删除"); return; } HeroNode2...
  • 双端链表  对于单项链表,我们如果想在尾部添加一个节点,那么必须从头部一直遍历到尾部,找到尾节点,然后在尾节点后面插入一个节点。这样操作很麻烦,如果我们在设计链表的时候多个对尾...如果链表为空,则直...

空空如也

空空如也

1 2 3 4 5 ... 16
收藏数 304
精华内容 121
关键字:

判断双向链表为空表