最新链表面试问题及其答案合集 - 面试题

下面列出了最常见的链接列表面试问题和答案。

1)简要说明链接列表。

链表可以定义为可以存储项目集合的线性数据结构。以另一种方式, 可以利用链接列表来存储相似类型的各种对象。列表中的每个元素或单元都表示为一个节点。每个节点都包含其数据和下一个节点的地址。它类似于一条链。链接列表用于创建图和树。

2)你将如何在图形视图中表示链接列表？

链表可以定义为其中每个元素都是单独对象的数据结构。链接列表元素不保留在连续位置。指针用于链接链表的元素。

列表中可用的每个节点由两项组成-数据本身和对序列中下一个节点的引用(也称为链接)。最后一个节点包括对null的引用。链接列表的起点称为列表的开头。应当注意, 头是对第一节点的引用, 而不是单独的节点。如果列表为空, 则将标头视为空引用。

3)存在几种类型的链表？

有多种类型的链接列表可用：

单链表
双链表
乘法链表
通报链表

4)简要说明单链表。

单链接列表包括包含数据字段和下一个字段的节点。下一个字段进一步指向节点行中的下一个节点。

换句话说, 单链接列表中的节点包含一个指向列表中下一个节点的指针。我们可以在单链表中执行插入, 删除和遍历等操作。

下面显示了一个单链列表, 其节点包含两个字段：整数值和指针值(指向下一个节点的链接)。

5)你对双链表有什么了解？

双链列表包含指向列表中的下一个节点以及上一个节点的指针(链接)。节点之间的两个链接可以称为”前进”和”后退”, 或者称为”下一个”和”上一个(上一个)”。下面显示了一个双向链接列表, 该列表的节点包含三个字段：整数值, 指向下一个节点的链接和指向上一个节点的链接。

一种技术(称为XOR链接)用于允许在每个节点中的单个链接字段的帮助下实现双向链接列表。但是, 此技术需要对地址执行某些操作的更多能力, 因此可能不适用于某些高级语言。

大多数现代操作系统使用双链表来维护对活动线程, 进程和其他动态对象的引用。

6)简要说明乘法链接列表。

在多重链接列表中, 每个节点都包含两个或更多链接字段。每个字段用于按同一组记录的不同顺序连接同一组记录。 “按姓名, 出生日期, 部门等”。

7)你将如何解释循环链表？

在链接列表的最后一个节点中, 链接字段通常包含一个空引用。循环链接列表中的最后一个节点包括指向第一个节点的指针, 而不是在列表的末尾包含空指针。在这种情况下, 该列表被称为”循环链接”。否则称为”开放”或”线性”。循环链接列表是最后一个指针指向或包含第一个节点地址的列表类型。

如果是圆形双向链接列表, 则第一个节点也指向列表的最后一个节点。

8)实现一个简单的链表需要多少个指针？

实现简单的链表通常需要三种类型的指针：

“头”指针, 用于指向列表中记录的开始。
一个”尾巴”指针, 用于指向最后一个节点。最后一个节点中的关键因素是其后续指针不指向任何内容(NULL)。
每个节点中的一个指针, 用于指向下一个节点元素。

9)如何表示一个链表节点？

表示链接列表节点的最简单方法是使用typedef结构包装数据和链接。然后进一步将结构分配为指向下一个节点的Node指针。

C语言中的表示示例可以定义为：

/*ll stands for linked list*/
typedefstructll
{
int data;
structll *next;
} Node

10)链接列表引用哪种类型的内存分配？

动态内存分配用于链接列表。

11)你对链接列表中的遍历了解多少？

术语”遍历”是指处理列表中存在的每个元素的操作。

12)链表和线性数组之间的主要区别是什么？

Linked List	线性阵列
删除和插入很困难。
线性阵列在执行删除和插入时需要移动节点。
在线性阵列中, 浪费了空间。
线性阵列有点贵。
不能减少或扩展。
为了利用线性阵列中的每个元素, 需要相同的时间。
在连续的存储位置中, 存储了元素。
我们可以直接达到任何特定元素。

13)链接列表中的虚拟头包含什么？

在链接列表中, 虚拟头由实际数据的第一条记录组成。

14)提到链表的一些应用？

链表的主要应用很少是：

链接列表使我们可以实现队列, 堆栈, 图形等。
链接列表使我们可以在列表的开头和结尾插入元素。

15)如何在单链列表的开头插入节点？

要将节点插入列表的开头, 我们需要执行以下步骤：

创建一个新节点
通过将头指针分配给新节点的下一个指针来插入新节点
更新头指针以指向新节点

Node *head;
voidInsertNodeAtFront(int data)
{
/* 1. create the new node*/
Node *temp = new Node;
temp->data = data;
/* 2. insert it at the first position*/
temp->next = head;
/* 3. update head to point to this new node*/
head = temp;
}

16)命名一些使用链表的应用程序。

队列和堆栈都可以使用链表来实现。使用链表的其他一些应用程序包括二叉树, 跳过, 展开链表, 哈希表等。

17)区分单链表和双链表？

双链列表节点由三个字段组成：一个整数值和两个指向两个其他节点的链接(一个指向最后一个节点, 另一个指向下一个节点)。

另一方面, 单链接列表由仅指向下一个节点的链接组成。

18)链表的主要优点是什么？

链接列表的主要优点是我们不需要为列表指定固定大小。我们添加到链中的元素越多, 链就越大。

19)有人如何将一个项目添加到列表的开头？

在列表的开头添加一个项目, 我们需要执行以下步骤：

创建一个新项目并设置其值。
链接新创建的项目, 使其指向列表的开头。
将列表的开头设置为我们的新项。

如果使用函数来执行此操作, 则需要更改head变量。

20)有人如何在链表的末尾插入节点？

这种情况有点困难, 因为它取决于实现的类型。如果我们有一个尾指针, 那很简单。如果我们没有尾部指针, 则必须遍历该列表, 直到到达末尾(即, 下一个指针为NULL)。然后, 我们需要创建一个新节点, 并使最后一个节点的下一个指针指向该新节点。

voidInsertNodeAtEnd(int data)
{
   /* 1. create the new node*/
    Node *temp = new Node;
temp->data = data;
temp->next = NULL;
    /* check if the list is empty*/
if (head == NULL)
    {
head = temp;
return;
    }
else
    {
        /* 2. traverse the list till the end */
        Node *traveler = head;
while (traveler->next != NULL)
traveler = traveler->next;
        /* 3. Set up the last node to point to this new node*/
traveler->next = temp;
    }
}

21)有人如何在链表的随机位置插入节点？

如果要在第一个位置或空白列表中插入节点, 则可以轻松插入该节点。否则, 我们需要遍历列表, 直到到达指定位置或列表的末尾。然后我们可以插入一个新节点。在中间位置插入节点有点困难, 因为我们必须确保以正确的顺序执行指针分配。要在中间插入一个新节点, 请按照下列步骤操作：

首先, 我们需要将新节点的下一个指针设置为该节点之前的那个节点。
然后, 我们需要将前一个节点的下一个指针分配给新节点的起始位置。

检查以下示例：

voidInsertNode(int data, int position)
{
/* 1. create the new node */
    Node *temp = new Node;
temp->data = data;
temp->next = NULL;
    /* confirm if the position to insert is first or the list is empty */
if ((position == 1) || (head == NULL))
    {
        // set up the new node pointing to head
        // because list may not be empty
temp->next = head;
        // Now point head to the first node
head = temp;
return;
    }
else
    {
   /* 2. traverse to the required position */
    Node *t = head;
intcurrPos = 2;
while ((currPos< position) && (t->next != NULL))
        {
            t = t->next;
currPos++;
        }
 /* 3. now we are at the required location */
        /* 4 first set up the pointer for the new node */
temp->next = t->next;
        /* 5 now set up the previous node pointer */
t->next = temp;
    }
}

22)我们如何从单链列表中删除第一个节点？

要从单链列表中删除第一个节点, 我们需要执行以下步骤：

将第一个节点地址复制到某个临时变量。
将头更改为链接列表的第二个节点。
删除第一个节点到第二个节点的连接。
删除temp并释放第一个节点占用的内存。

23)我们如何从链表中删除任何特定的节点？

如果我们要删除的节点是根节点, 我们可以轻松地将其删除。要删除中间节点, 我们必须有一个指向该节点的指针, 该指针位于要删除的节点之前。因此, 如果位置非零, 那么我们将运行位置循环并获取指向前一个节点的指针。

下面给出的步骤用于从列表中的指定位置删除节点：

设置头部以指向头部指向的那个节点。
将列表遍历到所需位置或直到列表末尾(以先到者为准)
我们需要将前一个节点指向下一个节点。

24)我们怎样才能扭转一个单链表？

要反转单链列表, 我们需要遍历该列表。我们需要在每一步都反向链接, 例如在第一次迭代之后, 头将指向null, 下一个元素将指向头。在遍历结束时, 当我们到达链表的尾部时, 尾部将开始指向倒数第二个元素, 并将成为新的头部。这是因为我们可以进一步遍历该特定节点中的所有元素。

下面给出的步骤可用于反转单链列表：

首先, 我们需要设置一个指向第一个节点(即current = head)的指针(* current)。
前进直到当前！ = null(直到列表末尾)。
设置另一个指向下一个节点的指针(* next)(即next = current-> next> next = result
将* next的引用保留在一个临时变量(* result)中, 即current-> next = result
用当前值交换结果值, 即result = current
然后将当前值与下一个交换, 即current = next。
返回结果并从步骤2开始重复。

链表也可以通过使用递归来反转, 从而避免使用临时变量。

25)如何删除链表中的循环？快速指针和慢速指针的功能是什么？

检测和删除链接列表中的循环的主要概念是使用两个指针(一个慢速指针和一个快速指针)。慢速指针一次遍历单个节点, 而快速指针一次遍历两倍于第一个节点。如果链表中包含循环, 则快慢指针将位于同一节点。另一方面, 如果列表中没有包含循环, 则显然快速指针将在慢速指针之前到达末尾。如果这两个指针相遇, 则检测到循环。如果检测到循环, 循环的开始可以帮助我们从链接列表中删除检测到的循环。它被称为弗洛伊德的循环查找算法。给定的图显示了循环在链表中的样子：

26)你希望在单链表和双链表之间遍历元素列表吗？

与单链列表相比, 双链列表需要每个节点更多的空间。在双向链接列表中, 诸如插入和删除之类的基本操作较为昂贵, 但它们易于操作, 因为它们可以在两个方向上快速便捷地顺序访问列表。但是, 双向链接列表不能用作持久性数据结构。因此, 双向链表将是遍历节点列表的更好选择。

27)在链表中插入新节点时, 空闲节点在哪里可用？

如果在链接列表中插入了新节点, 则在可用列表中会找到空闲节点。

28)对于哪个标题列表, 最后一个节点包含空指针？

对于接地的标头列表, 你将找到包含空指针的最后一个节点。

29)如何遍历Java中的链表？

在Java中有几种遍历链表的方法, 例如, 我们可以使用传统的for, while或do-while循环并遍历链表, 直到到达链表的末尾。另外, 我们可以使用Java 1.5的增强型for循环或迭代器遍历Java中的链表。从JDK 8开始, 我们可以选择使用java.util.stream.Stream遍历链接列表。

30)如何计算Java中单链表的长度？

我们可以遍历链表, 并保留节点数, 直到到达链表的末尾, 下一个节点为空。计数器的值被视为链表的长度。

31)某人如何显示从头到尾的单链接列表？

必须遵循以下步骤才能显示从头到尾的单链接列表：

使用create()创建一个链表。
存储在全局变量” start”中的地址无法更改, 因此必须声明一个类型为node的临时变量” temp”。
为了从头到尾遍历, 应在指针变量即temp中分配起始节点的地址。

struct node *temp;  //Declare temp variable
temp = start;       //Assign Starting Address to temp

如果temp为NULL, 则意味着将访问最后一个节点。

while(temp!=NULL)
{
printf("%d", temp->data);
temp=temp->next;
}

32)提到链表的一些缺点。

链表的一些重要缺点如下：

不允许随机访问。我们需要从第一个节点开始顺序访问元素。因此, 我们无法使用链接列表执行二进制搜索。
列表的每个元素都需要更多的指针存储空间。
O(n)索引访问速度很慢, 因为按索引访问链接列表意味着我们必须递归遍历列表。
本地性差, 用于链表的内存分散在混乱的地方。

33)提及用于Java中的链表类的软件包。

Java中用于链接列表的软件包是java.util。

34)提到Java中由链表实现的一些接口。

Java链表实现的一些主要接口是：

可序列化
队列
list
可克隆的
采集
和
可迭代的

35)如何使用Java中的Stack查找两个链表的总和？

为了计算链接列表的总和, 我们计算在相同位置的节点上保存的值的总和。例如, 我们在两个链表的第一个节点上添加值, 以找到结果链表的第一个节点的值。如果两个链表的长度都不相等, 那么我们仅添加较短链表中的元素, 并复制长链表中其余节点的值。

工作/人力资源面试问题

jQuery面试问题

Java OOP面试问题

JSP面试问题

休眠面试问题

SQL面试题

Android面试题

MySQL面试问题

删除和插入都很容易。

链表在执行删除和插入操作时不需要移动节点。

在链接列表中, 不会浪费空间。

链表并不昂贵。

它可以根据要求扩展或减少选项。

要利用链表中的每个元素, 需要花费不同的时间。

链表中的元素可能会或可能不会存储在连续的内存位置中。

要到达特定节点, 我们需要遍历该特定节点之前的所有节点。

面试技巧

JavaScript面试问题

Java基础面试问题

Servlet面试问题

春季面试问题

PL / SQL面试问题

Oracle面试问题

SQL Server面试问题