一、序言
数据结构在大学都学过,由于大学认识不够,对这个有点酱油了,很多东西都是知道其概念,当然基本的应用也会,但是偶尔的面试等一些地方的应用,还是不够,这里再复习一些知识,给大家分享,知识来源于数据结构的书和网上的东西。
二、抽象数据类型
ADT(abstract data type)是带有一组操作的的的一些对象的集合。对于集合的ADT,我的理解是:拥有对数据的存放结构的定义(比如Node、List),是一种自定义的数据结构,同时含有对这些元素进行操作的描述(比如:add、remove、insert),这些都是没有具体实现,但是可以通过这些定义和描述我们可以进行分析和研究,同时给实现留下空间,JAVA 集合里面对这块做了多种实现。
三、简单链表
简单链表包含了存储元素和指向下一个元素的“指针”,这里我们仅通过图进行简单描述:
可以看出,上面有一个头节点,通过next 连接和后续节点,最后一个节点指向null.我们可以创建自己的单链表:
// 我们先定义一个简单的节点形式的结构 public class Node<T> { T element; Node<T> next; }
// 通过节点,可以实现简单链表 public class LinkNode<T> extends Node<T>{ // 头结点 private Node<T> head = null; public LinkNode(){head = new Node<T>();} // 基本方法 void add(Node<T> node){} // 移除 void remove(Node<T> node){} // 指定位置添加 void insert(Node<T> node,int index){} // 查找 Node<T> find(T t){return null;} }
四、操作分析:
1.add () 一个节点:下图可以看出我们默认添加到头节点,讲原来head 结点的执行改变,同时将新节点的next 指向下个节点就行了。当然我们也可以放在末尾,原理类似。
2.remove() 移除:假设我要移除第二个节点,那么仅仅需要将第一个节点的next 指向第三个就行了。
3.find(Node node) 查找:链表的查找会从头开始遍历,和每一个元素进行匹配,循环依次next,显然这个是线性查找,效率没数组那么快,当然在设计过程中,我们可以通过插入时排序,数组存放元素灯方式节省时间,当然会浪费一部分插入的时间,或者存储空间。
4.insert(Node node,int index) 指定位置插入,这个就不贴图了,可以在next 移动的时候记录下标,在下标为index 的位置插入就行了。
五、单向链表反转:这里的反转分为有头结点和没有头节点的情况,但是原理都差不多,这里为了上图理 解,我们用有头节点的情况。
1.先判断头节点的next 是否存在元素节点,如果存在元素的情况下,还得判断第一个元素的next 是否还有节点,如果没有,表示只有一个节点,直接就返回了,没必要反转。
2.在有头节点的情况,原理差不多,我们先把头结点隔离开,然后把第一个节点断开,并且指向null,为了能继续找到下面的节点,我们需要一个临时变量,将后面的节点连接起来,现在的图为:
3.然后我们将cur 指向下一个节点C,节点B 的next 指向A(first),同时移动之后将B作为first节点,等待下一次连接,如图:
4.反复执行该操作,直到最后一个节点(C)指向B,这时候cur = null,first = C节点,最后将头节点head 指向 first 节点就行了。
Node<T> reverse(Node<T> node){ Node<T> first; Node<T> cur; // 判断是否有下一个节点(A),临时节点保存(B后续节点) if((first = node.next) == null || (cur = first.next) == null){ return node; } // 头节点断开 node.next = null; // 断开第一个有效节点(A) first.next = null; while(cur != null){ Node<T> temp = cur.next; // 当前节点的指针,反向指向前一个 cur.next = first; // 这个节点从新作为前节点,等待下一次反向 first = cur; // 从新指定当前节点 cur = temp; } node.next = first; return node; }
4. 对于无头节点的链表,没那么麻烦,仅仅断开第一个节点,从后往前就行了。
小结:
1.简单链表,相信大家都懂,各种实现也比我清楚,之所以写这个东西,是因为上次面试有个题,我写了20分钟,想着如何精简代码,如何快速,最后都不敢确定写正确与否,很受打击,也狠狠的鄙视下自己。当然这并不能说明我不会,像很多的排序算法一样,也许我们都知道原理,但是偶尔的一道算法题,不让你上机测试,直接写代码,我相信会有很多人写出来,都不敢保证自己的写的一定正确!确实有一定状态、运气等成分,但是有些基础的东西,以为掌握了,但是在没完全掌握的情况下,还是得进行一些复习吧。
2.最近看大家聊得最多的什么分布式、高并发、大数据,包括自己也在买书研究,往往忽略的一些基础,也给大家提个醒,抽时间再深入下基础,这些框架实现原理也是基础牢靠了,自己也能实现的,没想象的那么难,最后还是希望大家开心的工作吧~。~
相关推荐
### 数据结构之链表详解 #### 一、链表基本概念 **链表**是一种常见的数据结构,它通过一组地址不连续的存储单元来存储线性表中的各个数据元素。链表中的每个元素称为**结点**,这些结点不仅包含实际的数据信息,...
数据结构中的链表是一种重要的线性数据结构,它不同于数组,使用一组任意的存储单元来存储线性表的各个数据元素。链表的每个元素,我们称之为“结点”,不仅包含实际的数据信息,还包含一个指向下一个元素的链接,...
双向链表是一种特殊的数据结构,它在编程中具有重要的应用。本文将深入探讨双向链表的概念,实现,以及如何进行基本操作。 双向链表,顾名思义,是一种链式存储结构,其中每个节点包含两个指针,一个指向前一个节点...
### 数据结构之链表 #### 一、链表概述 链表是一种常用的数据结构,在计算机科学领域占有极其重要的地位。链表与数组等其他数据结构相比,在某些操作上具有显著的优势,尤其是在动态调整大小和频繁插入删除的情况...
双向链表是一种特殊的数据结构,与单向链表不同,它在每个节点中包含两个指针,一个指向前一个节点,另一个指向后一个节点,从而允许在链表中进行双向遍历。本文将详细探讨如何实现双向链表,以及如何在其上执行冒泡...
《C语言数据结构-链表版学生管理系统》 在计算机科学中,数据结构是组织、存储和处理数据的重要工具,而链表作为一种基础且灵活的数据结构,被广泛应用于各种复杂算法和系统设计中。本项目《C语言数据结构-链表版...
一个简单的数据结构队列链表的VC程序,供学习使用
链表是一种常用的数据结构,它在计算机科学中扮演着重要的角色。相较于数组,链表的主要优点在于其动态性,可以在运行时高效地插入和删除元素,而无需移动大量的内存数据。在Java中,链表主要通过实现接口`List`、`...
链表是一种基础且重要的数据结构,它在计算机科学中扮演着关键角色,特别是在处理动态数据集合时。在C语言中,链表不像是数组那样在内存中连续存储元素,而是通过一系列分散的内存块(称为节点)来表示数据。每个...
数据结构-Java中实现一个简单的链表结构,通过定义一个节点类(Node),然后定义一个链表类(LinkedList)来管理节点,简单易懂,适合初学数据结构的同学掌握基本数据结构的使用实现原理。
2. **链表**:链表是线性数据结构,但元素在内存中并不连续。它由节点组成,每个节点包含数据和指向下一个节点的引用。单链表、双链表、循环链表等都是链表的不同形式,这些都会在课程中被详细讲解。 3. **栈与队列...
数据结构是计算机科学中的核心课程,它探讨了如何在计算机中高效地组织和管理数据,以便于进行各种操作。湖南大学的数据结构期末试题涵盖了这门课程的重要概念和技术,旨在检验学生对这些知识的理解和应用能力。以下...
顺序表是一种简单的数据结构,其中元素在内存中是连续存储的,就像数组一样。顺序表的优点是访问速度快,因为可以通过索引直接访问任何位置的元素。然而,插入和删除操作可能涉及大量元素的移动,这在处理大量数据时...
数据结构-数组&链表&队列&堆栈代码示例,附有详细的注释说明,简单移动,适合初学者参考学习。
线性表是一种基础的数据结构,它是由n(n>=0)个相同类型元素构成的有限...此外,了解链表的优缺点有助于在实际问题中选择合适的数据结构,例如在需要高效插入和删除但不关心随机访问的情景下,链表是一个很好的选择。
链表是一种常见的线性数据结构,它通过节点之间的连接来表示数据项。与数组不同,链表中的元素不必存储在连续的内存空间中。每个节点包含两部分:数据部分(用于存储实际的数据)和指针部分(用于指向下一个节点的...
数据结构链表的课程设计 本资源是关于数据结构链表的课程设计,包括了链表的程序源代码。下面是对标题、描述、标签和部分内容的详细解释: 标题:数据结构链表的课程设计 这个标题表明了该资源的主要内容是关于...
链表是一种基础且重要的数据结构,它在计算机科学中扮演着至关重要的角色。与数组不同,链表的元素不连续存储在内存中,而是通过节点之间的指针链接起来。链表有多种类型,每种都有其独特的特性和应用场景。下面我们...