线性表概述及单链表的Java实现

简介: 线性表概述及单链表的Java实现一、线性表概述线性表是指一组数据元素之间具有线性关系的元素序列,它表现为:除第一个元素没有直接前驱元素、最后一个元素没有直接后继元素外,其余所有元素都有且仅有一个直接前驱元素和直接后继元素。

线性表概述及单链表的Java实现
一、线性表概述
线性表是指一组数据元素之间具有线性关系的元素序列,它表现为:除第一个元素没有直接前驱元素、最后一个元素没有直接后继元素外,其余所有元素都有且仅有一个直接前驱元素和直接后继元素。

根据存储结构的不同,线性表可以分为顺序存储和链式存储。

1、顺序存储
顺序存储结构是指用一段地址连续的存储单元依次存储线性表的数据元素。

数组就是采用顺序存储结构来存储的,数组元素的保存和读取操作的时间复杂度都是O(1),而插入和删除操作的时间复杂度为O(n),其优缺点如下:

优点 缺点
快速存取,时间复杂度O(1) 插入、删除时,时间复杂度较高为,O(n)
无需为表示元素之间的逻辑关系而增加额外的存储空间 存储空间固定,不易扩展,容易造成空间的浪费
2、链式存储
链式存储是指数据元素在内存空间中的存储地址可以是不连续的,元素之间的逻辑关系通过其附带的指示信息来进行关联。

单链表、双向链表、循环链表等都是采用链式存储结构进行存储的。

对于单链表来说,单个结点分为数据域和指针域,指针域附带的指示信息是下一个结点的存储地址。

单链表元素的读取、插入和删除的时间复杂度都是O(n),在插入和删除的操作上,如果我们不知道所要操作结点的指针,那么相比顺序存储结构的数组没有优势,在知道要操作结点的指针的情况下,对于插入或删除越频繁,单链表的效率优势就越明显。

比如插入10个元素,对于数组来说,每插入一个元素都要移动n-1个结点,每次的时间复杂度都是O(n),而对于单链表来说,只需要在第一次插入时找到目标位置结点的指针,后续插入都只需要通过移动指针来完成,时间复杂度为O(1)。

二、单链表的Java实现
1、定义单链表的存储结构
public class Node {

E element;
Node next;

Node() {
}

Node(E e) {
    this.element = e;
    this.next = null;
}

}
一个Node结点包含两个属性,E element为存储的数据,指定为泛型;Node next为逻辑上的下一个结点的存储地址。

2、定义操作接口
public interface Collection {

void add(E e);

void insert( E e, int index);

void delete(int index);

E get(int index);

void modify( E e,int index);

boolean isEmpty();

int size();

}
为集合、列表类操作定义一个包含公有行为的接口。

3、实现单链表
单链表的插入和删除操作可以抽象成两个步骤:

(1)找到目标结点

通过头节点进行遍历,直到找到目标结点;

(2)插入或删除;

插入:

//front为index - 1结点,即要插入位置的前一个结点
node.next = front.next;
front.next = node;
删除:

//front为index - 1结点,即要删除位置的前一个结点
node = front.next;
front.next = node.next;
//释放node结点
node = null;
单链表完整实现如下:

public class LinkedList implements Collection {

/**
 * 头指针
 */
private Node<E> head;

/**
 * 尾指针
 */
private Node<E> tail;

private int size;

public LinkedList() {
    //初始化时创建空的头指针和尾指针,并指向同一个节点,后续增加元素时,尾指针后移,但头指针一直不变
    head = new Node<E>();
    tail = head;
    size = 0;
}

@Override
public void add(E e) {
    Node node = new Node<E>(e);
    //设置尾指针的下一个节点为node
    tail.next = node;
    //设置node为新的尾指针
    tail = node;
    //长度+1
    size++;
}

@Override
public void insert(E e, int index) {
    verifyIndex(index, size);
    Node node = new Node<E>(e);
    //先遍历找到index-1结点,然后在index-1结点插入,复杂度O(n)
    int i = 0;
    //index - 1结点
    Node front = head;
    while (i < index) {
        front = front.next;
        i++;
    }
    node.next = front.next;
    front.next = node;
    size++;
    System.out.println(this.toString());
}

@Override
public void delete(int index) {
    verifyIndex(index, size - 1);
    //找到index-1节点
    int i = 0;
    Node front = head;
    while (i < index) {
        front = front.next;
        i++;
    }
    Node target = front.next;
    front.next = target.next;
    target = null;
    size--;
    System.out.println(this.toString());
}

@Override
public E get(int index) {
    verifyIndex(index, size - 1);
    Node node = head;
    int i = 0;
    while (i <= index) {
        node = node.next;
        i++;
    }
    return (E) node.element;
}

@Override
public void modify(E e, int index) {
    verifyIndex(index, size - 1);
    Node node = head;
    int i = 0;
    while (i <= index) {
        node = node.next;
        i++;
    }
    node.element = e;
    System.out.println(this.toString());
}

@Override
public boolean isEmpty() {
    return size <= 0;
}

@Override
public int size() {
    return 0;
}

/**
 * 判断操作的索引是否合法,
 * @param index
 * @param end   右边界,插入时允许在末尾插入,即end = size
 * @return
 */
private void verifyIndex(int index, int end) {
    if (index < 0 || index > end) {
        throw new IndexOutOfBoundsException("invalid index for LinkedList:" + this.toString());
    }
}

@Override
public String toString() {
    Node node = head;
    StringBuilder stringBuilder = new StringBuilder();
    while (node.next != null) {
        node = node.next;
        stringBuilder.append(node.element + " ");
    }
    return stringBuilder.toString();
}

}
Github下载地址
原文地址https://www.cnblogs.com/sqchen/p/10778472.html

相关文章
|
24天前
|
Java
环形数组链表(java)
环形数组链表(java)
11 0
|
1月前
|
算法
数据结构和算法学习记录——线性表之双向链表(上)-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数
数据结构和算法学习记录——线性表之双向链表(上)-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数
24 0
|
22天前
|
设计模式 算法 Java
Java设计模式:核心概述(一)
Java设计模式:核心概述(一)
|
2月前
|
数据采集 Java 数据处理
Java流与链表:探索java.util.stream与LinkedList的交汇点
本文探讨了Java中流(Streams)与链表(LinkedList)的结合使用,展示了如何通过流处理LinkedList以实现高效数据操作。示例代码包括LinkedList的基本操作、使用Stream进行过滤和映射,以及结合HttpClient和代理IP实现网络爬虫。代理IP有助于绕过反爬机制,提高爬取效率。通过结合这些技术,开发者能编写出更简洁、高效的代码。
Java流与链表:探索java.util.stream与LinkedList的交汇点
|
1月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
14 2
|
1月前
|
算法 Java C语言
【经典算法】LeetCode25:K 个一组翻转链表(Java/C/Python3,Hard)
【经典算法】LeetCode25:K 个一组翻转链表(Java/C/Python3,Hard)
11 1
|
1月前
|
算法 安全 Java
【经典算法】LeetCode 21:合并两个有序链表Java/C/Python3实现含注释说明,Easy)
【经典算法】LeetCode 21:合并两个有序链表Java/C/Python3实现含注释说明,Easy)
18 1
|
24天前
|
Java
HashTab基于链表简单实现(java,不包含扩容)
HashTab基于链表简单实现(java,不包含扩容)
10 0
|
24天前
|
Java
单向环形链表-约瑟夫问题(java)
单向环形链表-约瑟夫问题(java)
8 0
|
24天前
|
Java
双向链表增、删、改、按序号插入(java)
双向链表增、删、改、按序号插入(java)
14 0