`
greemranqq
  • 浏览: 974718 次
  • 性别: Icon_minigender_1
  • 来自: 重庆
社区版块
存档分类
最新评论

数据结构--简单链表

阅读更多

一、序言

       数据结构在大学都学过,由于大学认识不够,对这个有点酱油了,很多东西都是知道其概念,当然基本的应用也会,但是偶尔的面试等一些地方的应用,还是不够,这里再复习一些知识,给大家分享,知识来源于数据结构的书和网上的东西。

 

二、抽象数据类型

       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.最近看大家聊得最多的什么分布式、高并发、大数据,包括自己也在买书研究,往往忽略的一些基础,也给大家提个醒,抽时间再深入下基础,这些框架实现原理也是基础牢靠了,自己也能实现的,没想象的那么难,最后还是希望大家开心的工作吧~。~

  • 大小: 15.7 KB
  • 大小: 19.5 KB
  • 大小: 18.3 KB
  • 大小: 23.6 KB
  • 大小: 22.6 KB
  • 大小: 20.9 KB
0
0
分享到:
评论

相关推荐

    数据结构-链表 数据结构 链表

    ### 数据结构之链表详解 #### 一、链表基本概念 **链表**是一种常见的数据结构,它通过一组地址不连续的存储单元来存储线性表中的各个数据元素。链表中的每个元素称为**结点**,这些结点不仅包含实际的数据信息,...

    数据结构-链表

    数据结构中的链表是一种重要的线性数据结构,它不同于数组,使用一组任意的存储单元来存储线性表的各个数据元素。链表的每个元素,我们称之为“结点”,不仅包含实际的数据信息,还包含一个指向下一个元素的链接,...

    数据结构-双向链表

    双向链表是一种特殊的数据结构,它在编程中具有重要的应用。本文将深入探讨双向链表的概念,实现,以及如何进行基本操作。 双向链表,顾名思义,是一种链式存储结构,其中每个节点包含两个指针,一个指向前一个节点...

    0基础学数数据结构--链表

    ### 数据结构之链表 #### 一、链表概述 链表是一种常用的数据结构,在计算机科学领域占有极其重要的地位。链表与数组等其他数据结构相比,在某些操作上具有显著的优势,尤其是在动态调整大小和频繁插入删除的情况...

    数据结构---双向链表的实现

    双向链表是一种特殊的数据结构,与单向链表不同,它在每个节点中包含两个指针,一个指向前一个节点,另一个指向后一个节点,从而允许在链表中进行双向遍历。本文将详细探讨如何实现双向链表,以及如何在其上执行冒泡...

    C语言数据结构-链表版学生管理系统

    《C语言数据结构-链表版学生管理系统》 在计算机科学中,数据结构是组织、存储和处理数据的重要工具,而链表作为一种基础且灵活的数据结构,被广泛应用于各种复杂算法和系统设计中。本项目《C语言数据结构-链表版...

    数据结构-链表队列-VC源代码

    一个简单的数据结构队列链表的VC程序,供学习使用

    链表(数据结构--Java版)

    链表是一种常用的数据结构,它在计算机科学中扮演着重要的角色。相较于数组,链表的主要优点在于其动态性,可以在运行时高效地插入和删除元素,而无需移动大量的内存数据。在Java中,链表主要通过实现接口`List`、`...

    数据结构-链表的C语言使用

    链表是一种基础且重要的数据结构,它在计算机科学中扮演着关键角色,特别是在处理动态数据集合时。在C语言中,链表不像是数组那样在内存中连续存储元素,而是通过一系列分散的内存块(称为节点)来表示数据。每个...

    数据结构-Java中实现一个简单的链表结构

    数据结构-Java中实现一个简单的链表结构,通过定义一个节点类(Node),然后定义一个链表类(LinkedList)来管理节点,简单易懂,适合初学数据结构的同学掌握基本数据结构的使用实现原理。

    北大信息院数据结构--张铭

    2. **链表**:链表是线性数据结构,但元素在内存中并不连续。它由节点组成,每个节点包含数据和指向下一个节点的引用。单链表、双链表、循环链表等都是链表的不同形式,这些都会在课程中被详细讲解。 3. **栈与队列...

    湖南大学-数据结构-期末试题【2016-2019】.zip

    数据结构是计算机科学中的核心课程,它探讨了如何在计算机中高效地组织和管理数据,以便于进行各种操作。湖南大学的数据结构期末试题涵盖了这门课程的重要概念和技术,旨在检验学生对这些知识的理解和应用能力。以下...

    数据结构试验1-链表和顺序表

    顺序表是一种简单的数据结构,其中元素在内存中是连续存储的,就像数组一样。顺序表的优点是访问速度快,因为可以通过索引直接访问任何位置的元素。然而,插入和删除操作可能涉及大量元素的移动,这在处理大量数据时...

    数据结构-数组&链表&队列&堆栈代码示例程序

    数据结构-数组&链表&队列&堆栈代码示例,附有详细的注释说明,简单移动,适合初学者参考学习。

    数据结构学习--线性表及其应用--链表

    线性表是一种基础的数据结构,它是由n(n&gt;=0)个相同类型元素构成的有限...此外,了解链表的优缺点有助于在实际问题中选择合适的数据结构,例如在需要高效插入和删除但不关心随机访问的情景下,链表是一个很好的选择。

    链表----链表构造

    链表是一种常见的线性数据结构,它通过节点之间的连接来表示数据项。与数组不同,链表中的元素不必存储在连续的内存空间中。每个节点包含两部分:数据部分(用于存储实际的数据)和指针部分(用于指向下一个节点的...

    数据结构链表的课程设计

    数据结构链表的课程设计 本资源是关于数据结构链表的课程设计,包括了链表的程序源代码。下面是对标题、描述、标签和部分内容的详细解释: 标题:数据结构链表的课程设计 这个标题表明了该资源的主要内容是关于...

    链表---链表大集合

    链表是一种基础且重要的数据结构,它在计算机科学中扮演着至关重要的角色。与数组不同,链表的元素不连续存储在内存中,而是通过节点之间的指针链接起来。链表有多种类型,每种都有其独特的特性和应用场景。下面我们...

Global site tag (gtag.js) - Google Analytics