文档章节

Java数据结构(三):线性表之单链表

凌枫yong
 凌枫yong
发布于 2016/07/17 13:44
字数 839
阅读 5
收藏 0

链式存储结构存储线性表的方法是把存放数据元素的结点用指针域构造成链。指针是指向下一个节点的引用,由数据元素域和一个或若干个指针域组成的一个类称之为结点。链式存储结构的特点是数据元素间的逻辑关系表现在节点的链接关系上。

本例中实现的链表结构都是带头结点的。具体代码如下:
package datastructure.linear.linked;

import datastructure.exception.StructureException;
import datastructure.linear.AbstractList;

/** * @Description 单链表 * @author mastery * @Date 2015年6月30日下午6:11:17 * @param <T> */
public class SingleLinkedList<T> extends AbstractList<T> {

    class Node<T1> {

        T1 element;

        Node<T1> next;

        public Node(Node<T1> next) {
            super();
            this.next = next;
        }

        public Node(T1 element, Node<T1> next) {
            super();
            this.element = element;
            this.next = next;
        }

        @Override
        public String toString() {
            return element.toString();
        }
    }


    /** * 头结点,该结点没有参数值,只是指向第一个元素的结点 */
    private Node<T> head;

    /** * 当前的结点 */
    private Node<T> currentNode;

    public SingleLinkedList() {
        head = currentNode = new Node<T>(null);
        size = 0;
    }

    /** * 得到当前下标对应的结点 * @param index * @throws StructureException */
    public void indexNodeToCurrent(int index) throws StructureException {
        currentNode = head;
        if(index < -1 || index > size -1) {
            throw new StructureException("index参数异常!");
        }
        if(index == -1) {
            return ;
        }
        currentNode = head.next;
        int j = 0 ; 
        while(currentNode != null && j < index) {
            currentNode = currentNode.next;
            j++;
        }
    }

    @Override
    public void insert(int index, T t) throws StructureException {
        if(index < 0 || index > size) {
            throw new StructureException("index参数异常!");
        }
        // 得到当前下标的上一个结点
        indexNodeToCurrent(index-1);
        // 将新元素生成结点插入到当前结点下
        currentNode.next = new Node<T>(t , currentNode.next);
        size++;
    }

    @Override
    public void delete(int index) throws StructureException {
        if(isEmpty()) {
            throw new StructureException("链表为空");
        }
        if(index < 0 || index > size) {
            throw new StructureException("index参数异常");
        }
        indexNodeToCurrent(index-1);
        Node<T> twoNextNode = currentNode.next.next;
        currentNode.next = twoNextNode;
        size--;
    }

    @Override
    public T get(int index) throws StructureException {
        if(isEmpty()) {
            throw new StructureException("链表为空");
        }
        if(index < 0 || index > size) {
            throw new StructureException("index参数异常!");
        }
        indexNodeToCurrent(index);
        return currentNode.element;
    }

}

单链表的插入和删除操作的时间效率分析方法和顺序表的插入和删除操作的时间效率分析方法类同,差别是单链表的插入和删除操作不需移动数据元素,只需比较数据元素。
要说明的是,虽然单链表插入和删除操作的时间复杂度与顺序表插入和删除操作的时间复杂度相同,但是,顺序表插入和删除操作的时间复杂度指的是移动数据元素的时间复杂度,当数据元素占据的内存空间比较大时,这要比单链表插入和删除操作比较数据元素花费的时间大一个常数倍。另外,单链表求数据元素个数操作的时间复杂度为O(n).

与顺序表相比,单链表的主要有点是不需要预先确定数据元素的最大个数,插入和删除时不需要移动元素;主要缺点三每个结点中要有一个指针域,因此,空间单元利用效率不高。此外,单链表操作的算法比较复杂。

测试类如下:

package datastructure.linear.linked;

import static org.junit.Assert.*;

import org.junit.Test;

import datastructure.exception.StructureException;
import datastructure.linear.List;
import datastructure.linear.linked.SingleLinkedList;

public class SingleLinkedListTest {

    @Test
    public void testSingleLinkedList() throws StructureException {
        List<Integer> list = new SingleLinkedList<Integer>();
        for(int i = 0 ; i < 10 ; i ++) {
            list.insert(i, i+1);
        }
        list.delete(0);
        for(int i = 0 ; i < list.size() ; i++) {
            System.out.print(list.get(i) + " ");
        }
    }

    @Test
    public void testIndexNodeToCurrent() {
        fail("尚未实现");
    }

    @Test
    public void testInsert() {
        fail("尚未实现");
    }

    @Test
    public void testDelete() {
        fail("尚未实现");
    }

    @Test
    public void testGet() {
        fail("尚未实现");
    }

}

本文转载自:http://blog.csdn.net/u011990285/article/details/46710669

共有 人打赏支持
凌枫yong
粉丝 1
博文 65
码字总数 0
作品 0
南昌
私信 提问
《数据结构与算法系列》合集整理

《数据结构与算法系列》合集整理 整理来自博客园skywang12345,以下摘自作者介绍: “最近抽空整理了"数据结构和算法"的相关文章。在整理过程中,对于每种数据结构和算法分别给出"C"、"C++"...

kaixin_code
2018/12/01
0
0
第一阶段:Java内功秘籍-线性表

前言 为什么要学习数据结构与算法,如果你学会了做安卓,javaweb,前端等,都是你的武功秘籍,但是如果你的内功不够好,再厉害的功夫也是白费。 数据结构和算法:什么是数据结构,什么是数据...

达叔小生
2018/08/06
0
0
数据结构(java版)学习笔记(一)——线性表

一、线性表的定义 线性表是n(n>=0)个具有相同特性的数据元素的有限序列。 线性表是最简单、最常用的一种数据结构 线性表属于线性结构的一种 如果一个数据元素序列满足: (1)除第一个和最...

Stars-one
2018/07/29
0
0
[LintCode] Linked List Cycle(带环链表)

描述 给定一个链表,判断它是否有环。 样例 给出 -21->10->4->5, tail connects to node index 1,返回 true。 这里解释下,题目的意思,在英文原题中,tail connects to node index 1 表示的...

honeymose
2018/12/16
0
0
算法和编程面试题精选TOP50!(附代码+解题思路+答案)

作者 | javinpaul 编译 | 王天宇、Jane 整理 | Jane 出品 | AI科技大本营 【导读】之前我们给同学们推荐了很多关于 Python 的面试资源,大家都表示很有用。这次营长表示要翻 Java 的牌子啦~...

AI科技大本营
2018/09/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

table边框样式

table{ border:0.5px solid #000; border-collapse:collapse; //去除边框间空隙}th,td{ border:0.5px solid #000;}...

学霸猫
16分钟前
1
0
分布式消息通讯Kafka原理分析(二)

本章重点: 1.消息的存储原理2.Partition的副本机制原理3.副本数据同步原理 消息的文件存储机制 通过如 下命令找到对应partition下的日志内容 [root@localhost ~]# ls /tmp/kafka-logs/f...

须臾之余
21分钟前
0
0
Vue Element表单绑定(四)常用操作整理

一、启用回车提交报单操作 在登录页面,使用回车提交表单操作一般是必要的一个操作。在 Element中如何使用呢,示例如下: 来个注意点: 1.button按钮的native-type设置为submit,而不是绑定c...

tianma3798
26分钟前
1
0
《大话数据结构》读后总结(七)

常见的时间复杂度 执行次数 函数阶 非正式术语 12 O(1) 常数阶 2n+3 O(n) 线性阶 3n^2+2n+1 O(n2) 平方阶 5log2n+20 O(logn) 对数阶 2n+3nlog2n+19 O(nlogn) nlogn阶 6n^3+2n^2+3n+4 O(n3) 立...

徐曙辉
27分钟前
0
0
three.js 事件交互

点击查看交互效果 在three.js中,展示的一切内容都是在canvas中绘制的,所以点击事件点击到物体上是无法获取点击对象的,要获取点击的对象要使用RayCaster,用于在三维空间中进行鼠标拾取,原...

tianyawhl
28分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部