链表
链表与数组的区别是链表中的元素顺序是有各对象中的指针决定的,相邻元素之间在物理内存上不一定相邻。采用链表可以灵活地表示动态集合。链表有单链表和双链表及循环链表。书中着重介绍了双链表的概念及操作,双链表L的每一个元素是一个对象,每个对象包含一个关键字和两个指针:next和prev。链表的操作包括插入一个节点、删除一个节点和查找一个节点,重点来说一下双向链表的插入和删除节点操作,图例如下:
链表是最基本的数据结构,凡是学计算机的必须的掌握的,在面试的时候经常被问到,关于链表的实现,百度一下就知道了。在此可以讨论一下与链表相关的练习题。
(1)在单链表上插入一个元素,要求时间复杂度为O(1)。
解答:一般情况在链表中插入一元素是在末尾插入的,这样需要从头遍历一次链表,找到末尾,时间为O(n)。要在O(1)时间插入一个新节点,可以考虑每次在头节点后面插入,即每次插入的节点成为链表的第一个节点。
(2)在单链表上删除一个给定的节点p,要求时间复杂度为O(1)。
解答:一般情况删除一个节点时候,我们需要找到该节点p的前驱节点q,需要对链表进行遍历,运行时间为O(n-1)。我们可以考虑先将q的后继节点s的值替换q节点值,然后删除s即可。如下图删除节点q的操作过程:
(3)单链表逆置,不允许额外分配存储空间,不允许递归,可以使用临时变量,执行时间为O(n)。
解答:这个题目在面试笔试中经常碰到,基本思想上将指针逆置。如下图所示:
(4)遍历单链表一次,找出链表中间节点。
解答:定义两个指针p和q,初始都指向链表头节点。然后开始向后遍历,p每次移动2步,q移动一步,当p到达末尾的时候,p正好到达了中间位置。
(5)用一个单链表L实现一个栈,要求push和pop的操作时间为O(1)。
解答:根据栈中元素先进后出的特点,可以在链表的头部进行插入和删除操作。
(6)用一个单链表L实现一个队列,要求enqueue和dequeue的操作时间为O(1)。
解答:队列中的元素是先进先出,在单链表结构中增加一个尾指针,数据从尾部插入,从头部删除。
3、有根树的表示
采用链表数据结构来表示树,书中先降二叉树的链表表示法,然后拓展到分支数无限制的有根数。先来看看二叉树的链表表示方法,用域p、left和right来存储指向二叉树T中的父亲、左孩子和右孩子的指针。如下图所示:
对于分支数目无限制的有根树,采用左孩子、右兄弟的表示方法。这样表示的树的每个节点都包含有一个父亲指针p,另外两个指针:
(1)left_child指向节点的最左孩子。
(2)right_sibling指向节点紧右边的兄弟。