专注于 JetBrains IDEA 全家桶，永久激活，教程
持续更新 PyCharm，IDEA，WebStorm，PhpStorm，DataGrip，RubyMine，CLion，AppCode 永久激活教程
当前位置：搜云库技术团队 Java汇总 正文

线性表以及Java代码实现

2020-08-11 分类：Java汇总 阅读(542)

什么是线性表

线性表：由同类型数据元素组成的有序序列的线性结构

  • 表中元素个数为表的长度
  • 线性表没有元素时，称为空表
  • 表起始位置叫做表头，表结束位置称表尾

它有三个特点：相同数据类型、有序、有限

线性表的存储结构分为两种：

  • 顺序存储结构：顺序表
  • 链式存储结构：链表

线性表的抽象数据类型(ADT)

package com.xgc.linearlist;

/**
 * 线性表的抽象数据类型
 * @author xgc
 *
 */
public interface LinearListADT {

    /**
     * 
     * @return 返回线性表的长度
     */
    public int size();

    /**
     * 
     * @return 返回线性表是否为空
     */
    public boolean isEmpty();

    /**
     * 获取指定索引的数据元素
     * @param i 索引
     * @return 指定索引的数据元素
     * @throws Exception 
     */
    public Object get(int i) throws Exception;

    /**
     * 将元素添加到线性表的指定索引处
     * @param i 索引
     * @param e 要添加的元素
     * @return 是否添加成功
     * @throws Exception 
     */
    public void add(int i, Object o) throws Exception;

    /**
     * 将元素添加到线性表的末尾
     * @param o 要添加的元素
     * @return 是否添加成功
     * @throws Exception 
     */
    public void add(Object o) throws Exception;

    /**
     * 移除指定索引处的元素
     * @param i 索引
     * @return 被移除的元素
     * @throws Exception 
     */
    public Object remove(int i) throws Exception;

    /**
     * 查看是否包含该元素
     * @param o 要查看的元素
     * @return 是否线性表含有此元素
     */
    public boolean contains(Object o);

    /**
     * 返回指定元素的索引
     * @param o 指定元素
     * @return 指定元素的索引
     */
    public int indexOf(Object o);
}

顺序表

线性表的顺序存储是指用一组地址连续的存储单元来存储数据元素，使得在逻辑结构上相邻的数据元素存储在相邻的物理存储单元。

采用顺序存储结构的线性表就叫顺序表。

优点：

1、 节省空间。分配给数据的存储空间全部用来存放数据，维护结点之间的逻辑顺序不需占用额外的存储空间。
2、 查找效率高。时间复杂度为O(1)。每一个元素对应一个序号，通过该序号可以直接计算出该元素的存储地址。

假设线性表的每个数据元素需要K个存储单元，并以该元素所占的第一个存储单元的地址作为数据元素的存储地址，那么线性表序号为i的数据元素的存储地址LOC(ai)与序号为i+1的数据元素的存储地址LOC(ai+1)之间的关系为：

> LOC(ai) = LOC(ai+1) + K

而且线性表序号为i的数据元素的存储地址为：

> LOC(ai) = LOC(a0) + i×K

其中 LOC(a0)为线性表0号元素的存储地址，也叫做线性表的起始地址。

缺点：

1、 插入和删除操作需要移动元素，效率低。

删除和删除操作的复杂度为`O(n)`

2、 必须提前分配固定数量的空间，当存储元素过少，会造成空间的浪费。

顺序表的代码实现

package com.xgc.linearlist.linkedlist.singlelinkedlist.withheadnode;

import com.xgc.linearlist.LinearListADT;

/**
 * 单链表，带有头结点
 */
public class SingleLinkedList implements LinearListADT{

    //头结点，为了编程方便
    private Node head = new Node();
    //元素个数
    private int size;

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

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

    @Override
    public Object get(int i) throws Exception {
        if(i<0 || i>=size) throw new Exception("索引越界");
        Node p = findNodeParent(i);
        return p.next.data;
    }

    @Override
    public void add(int i, Object o) throws Exception {
        if(i<0 || i>size) throw new Exception("索引越界");
        Node p = findNodeParent(i);
        //插入结点
        Node temp = p.next;
        p.next = new Node(o,temp);
        size++;
    }

    @Override
    public void add(Object o) throws Exception {
        this.add(size, o);
    }

    @Override
    public Object remove(int i) throws Exception {
        if(i<0 || i>=size) throw new Exception();
        Node p = findNodeParent(i);
        Node temp = p.next;
        p.next = p.next.next;
        size--;
        return temp.data;
    }

    @Override
    public boolean contains(Object o) {
        Node p = head;
        for(int i=0; i<size; i++) {
            p = p.next;
            if (o.equals(p.data)) {
                return true;
            }
        }
        return false;
    }

    @Override
    public int indexOf(Object o) {
        Node p = head;
        for(int i=0; i<size; i++) {
            p = p.next;
            if (o.equals(p.data)) {
                return i;
            }
        }
        return -1;
    }

    //根据给定的索引，找到该索引位置上的结点的父类
    private Node findNodeParent(int i) {
        Node p = head;
        for(int j=0; j<i; j++) {
            p = p.next;
        }
        return p;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        Node p = head;
        for (int i = 0; i < size; i++) {
            p = p.next;
            if (i != size-1) {
                sb.append(p.data + ",");
            }else {
                sb.append(p.data);
            }
        }
        sb.append("]");
        return sb.toString();
    }

}

测试

测试实现是否成功：

package com.xgc.linearlist.sequentiallist;

import com.xgc.linearlist.LinearListADT;

public class SequentialListTest {

    public static void main(String[] args) throws Exception {
        LinearListADT list = new ArrayList();
        System.out.println(list.isEmpty());

        list.add("xgc");
        list.add("xiaoli");
        System.out.println(list);
        System.out.println(list.isEmpty());

        list.remove(1);
        System.out.println(list);

        System.out.println(list.contains("xgc"));

        System.out.println(list.size());

        System.out.println((String)list.get(0));

        System.out.println(list.indexOf("xgc"));

        //测试扩容是否成功
        list.add("zhangsan");
        list.add("xiaoming");
        list.add("xiaohong");
        list.add("lili");
        System.out.println(list);
    }
}

执行结果如下：

true
[xgc,xiaoli]
false
[xgc]
true
1
xgc
0
[xgc,zhangsan,xiaoming,xiaohong,lili]

链表

跟顺序表不一样，链表是一种在存储单元上非连续、非顺序的存储结构。

数据元素的逻辑顺序是通过链表中的指针的链接顺序来实现的。

链表由结点(链表中的每一个数据元素叫做结点)组成。

链表也分为单链表、循环链表和双向链表。

优点：

1、 插入和删除效率比顺序表高。
2、 不会造成存储空间的浪费。只有当有元素的时候，才创建结点

缺点：

1、 存储密度没有顺序表高。因为它要花费额外的空间去存储指向下一个结点的指针。
2、 查询的效率比顺序表低。时间复杂度为O(n)

单链表

链表中最简单的就是单链表。

单链表中的结点分为两个域：一个是存储数据的数据域，一个是存储下一个结点地址的指针域。

链表中第一个结点的存储地址叫做头指针。整个链表的存取就是从头指针开始的。

我们先来看看带有头结点的单链表

65_1.png

那么什么是头结点，为什么需要头结点呢？

  • 头结点是链表的第一个结点，放在第一个元素结点(也叫首元结点)的前面。
  • 头结点是为了操作的统一和方便而设立的，其数据域一般没有意义。
  • 有了头结点，对第一个元素的结点的插入和删除的操作就和其他元素结点相同了。
  • 头结点不是链表必须的，但是建议加上，因为操作会比较方便。

如果链表中含有头结点，那么头指针指向的就是头结点。如果没有的话，那么指向的就是首元结点了。

我们来看看没有头结点的单链表：

65_2.png

单链表的代码实现

带有头结点

结点类

package com.xgc.linearlist.linkedlist.singlelinkedlist.withheadnode;

/**
 * 单链表的结点
 * @author xgc
 *
 */
public class Node {

    //数据域
    Object data;
    //指针域
    Node next;

    public Node() {}

    public Node (Object data) {
        this(data, null);
    }

    public Node (Object data, Node next) {
        this.data = data;
        this.next = next;
    }

}

单链表实现

package com.xgc.linearlist.linkedlist.singlelinkedlist.withheadnode;

import com.xgc.linearlist.LinearListADT;

/**
 * 单链表，带有头结点
 */
public class SingleLinkedList implements LinearListADT{

    //头指针，为了编程方便
    private Node head = new Node();
    //元素个数
    private int size;

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

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

    @Override
    public Object get(int i) throws Exception {
        if(i<0 || i>=size) throw new ArrayIndexOutOfBoundsException(i);
        Node p = findNodeParent(i);
        return p.next.data;
    }

    @Override
    public void add(int i, Object o) {
        if(i<0 || i>size) throw new ArrayIndexOutOfBoundsException(i);
        Node p = findNodeParent(i);
        //插入结点
        Node temp = p.next;
        p.next = new Node(o,temp);
        size++;
    }

    @Override
    public void add(Object o) {
        this.add(size, o);
    }

    @Override
    public Object remove(int i) {
        if(i<0 || i>=size) throw new ArrayIndexOutOfBoundsException(i);
        Node p = findNodeParent(i);
        Node temp = p.next;
        p.next = p.next.next;
        size--;
        return temp.data;
    }

    @Override
    public boolean contains(Object o) {
        Node p = head;
        for(int i=0; i<size; i++) {
            p = p.next;
            if (o.equals(p.data)) {
                return true;
            }
        }
        return false;
    }

    @Override
    public int indexOf(Object o) {
        Node p = head;
        for(int i=0; i<size; i++) {
            p = p.next;
            if (o.equals(p.data)) {
                return i;
            }
        }
        return -1;
    }

    //根据给定的索引，找到该索引位置上的结点的父类
    private Node findNodeParent(int i) {
        Node p = head;
        for(int j=0; j<i; j++) {
            p = p.next;
        }
        return p;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        Node p = head;
        for (int i = 0; i < size; i++) {
            p = p.next;
            if (i != size-1) {
                sb.append(p.data + ",");
            }else {
                sb.append(p.data);
            }
        }
        sb.append("]");
        return sb.toString();
    }

}
测试

单链表测试，和顺序表一样，只是更改了实现类

package com.xgc.linearlist.linkedlist.singlelinkedlist.withheadnode;

import com.xgc.linearlist.LinearListADT;

public class SingleLinkedListTest {

    public static void main(String[] args) throws Exception {
        LinearListADT list = new SingleLinkedList();
        System.out.println(list.isEmpty());

        list.add("xgc");
        list.add("xiaoli");
        System.out.println(list);
        System.out.println(list.isEmpty());

        list.remove(1);
        System.out.println(list);

        System.out.println(list.contains("xgc"));

        System.out.println(list.size());

        System.out.println((String)list.get(0));

        System.out.println(list.indexOf("xgc"));

        list.add("zhangsan");
        list.add("xiaoming");
        list.add("xiaohong");
        list.add("lili");
        System.out.println(list);
    }

}

运行结果，和顺序表一样

true
[xgc,xiaoli]
false
[xgc]
true
1
xgc
0
[xgc,zhangsan,xiaoming,xiaohong,lili]

双向链表

双向链表和单链表类似，区别在于结点的有三个域：一个是保存数据的数据域，二个是指针域，分别指向上一个结点和下一个结点。

跟单链表相比，双向链表的遍历效率会比单链表高。但是存储密度就比单链表低。

为了编程的方便，我们可以在双向链表中带两个哑元结点来实现。其中一个是头结点，另一个是尾结点。它们都不存放数据元素。

双向链表的代码实现

带有头结点和尾结点

双向链表的结点：

package com.xgc.linearlist.linkedlist.doublylinkedlist.withheadnodeandtailnode;

/**
 * 双向链表的结点
 * @author xgc
 *
 */
public class Node {

    Node prev;
    Object data;
    Node next;

    public Node() {
    }

    public Node(Object data) {
        this.data = data;
    }

    public Node(Node prev, Object data, Node next) {
        this.prev = prev;
        this.data = data;
        this.next = next;
    }
}

双向链表的实现：

package com.xgc.linearlist.linkedlist.doublylinkedlist.withheadnodeandtailnode;

import com.xgc.linearlist.LinearListADT;

public class DoublyLinkedList implements LinearListADT{

    //头指针
    private Node head;
    //尾结点
    private Node last;
    //结点个数
    private int size;

    public DoublyLinkedList() {
        head = new Node();
        last = new Node();
        head.next = last;
        last.prev = head;
        this.size = 0;
    }

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

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

    @Override
    public Object get(int i) throws Exception {
        if (i<0 || i>=size) {
            throw new Exception("索引越界");
        }
        Node p = head;
        for(int j=0; j<=i; j++) {
            p = p.next;
        }
        return p.data;
    }

    @Override
    public void add(int i, Object o) throws Exception {
        if(i<0 || i>size) {
            throw new Exception("索引越界");
        }
        Node p = head;
        for(int j=0; j<i; j++) {
            p = p.next;
        }
        Node temp = p.next;
        Node data = new Node(p, o, temp);
        p.next = data;
        temp.prev = data;
        size++;
    }

    @Override
    public void add(Object o) {
        Node temp = last.prev;
        Node data  = new Node(temp, o, last);
        temp.next = data;
        last.prev = data;
        size++;
    }

    @Override
    public Object remove(int i) throws Exception {
        if (i<0 || i>=size) {
            throw new Exception("索引越界");
        }
        Node p = head;
        for(int j=0; j<i; j++) {
            p = p.next;
        }
        //被删除的结点
        Node temp = p.next;
        temp.next.prev = p;
        p.next = temp.next;
        size--;
        return temp.data;
    }

    @Override
    public boolean contains(Object o) {
        Node p = head;
        for(int j=0; j<size; j++) {
            p = p.next;
            if (o.equals(p.data)) {
                return true;
            }
        }
        return false;
    }

    @Override
    public int indexOf(Object o) {
        Node p = head;
        for(int j=0; j<size; j++) {
            p = p.next;
            if (o.equals(p.data)) {
                return j;
            }
        }
        return -1;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        Node p = head;
        for (int i = 0; i < size; i++) {
            p = p.next;
            if (i != size-1) {
                sb.append(p.data + ",");
            }else {
                sb.append(p.data);
            }
        }
        sb.append("]");
        return sb.toString();
    }

}
测试
package com.xgc.linearlist.linkedlist.doublylinkedlist.withheadnodeandtailnode;

import com.xgc.linearlist.LinearListADT;

public class DoublyLinkedListTest {
    public static void main(String[] args) throws Exception {
        LinearListADT list = new DoublyLinkedList();
        System.out.println(list.isEmpty());

        list.add("xgc");
        list.add("xiaoli");
        System.out.println(list);
        System.out.println(list.isEmpty());

        list.remove(1);
        System.out.println(list);

        System.out.println(list.contains("xgc"));

        System.out.println(list.size());

        System.out.println((String)list.get(0));

        System.out.println(list.indexOf("xgc"));

        list.add("zhangsan");
        list.add("xiaoming");
        list.add("xiaohong");
        list.add("lili");
        System.out.println(list);
    }
}

测试结果

true
[xgc,xiaoli]
false
[xgc]
true
1
xgc
0
[xgc,zhangsan,xiaoming,xiaohong,lili]

循环链表

在上面的单链表和双向链表，最后一个结点的next指针域都赋值为null。

如果我们让最后一个结点的next指针域指向链表的第一个结点，那么这个链表就叫循环链表。

循环链表在单链表和双链表都可以实现。

循环单链表代码实现

下图是循环单链表的结构

65_3.png

Node结点

package com.xgc.linearlist.linkedlist.circularlinkedlist.circularsinglelinkedlist.withheadnode;

/**
 * 循环单链表的结点
 * @author xgc
 *
 */
public class Node {

    //数据域
    Object data;
    //指针域
    Node next;

    public Node() {}

    public Node (Object data) {
        this(data, null);
    }

    public Node (Object data, Node next) {
        this.data = data;
        this.next = next;
    }

}

循环单链表实现

package com.xgc.linearlist.linkedlist.circularlinkedlist.circularsinglelinkedlist.withheadnode;

import com.xgc.linearlist.LinearListADT;

public class CircularSingleLinkedList implements LinearListADT{

    //头指针
    private Node head;
    //首元结点
    private Node first;
    private int size;

    public CircularSingleLinkedList() {
        head = new Node();
        first = new Node();
        head.next = first;
        first.next = first;
    }

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

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

    @Override
    public Object get(int i) throws Exception {
        if(i<0 || i>=size) {
            throw new Exception("索引越界");
        }
        Node p = head;
        for(int j=0; j<=i; j++) {
            p = p.next;
        }
        return p.data;
    }

    @Override
    public void add(int i, Object o) throws Exception {
        if(i<0 || i>size) {
            throw new Exception("索引越界");
        }
        Node p = head;
        for(int j=0; j<i; j++) {
            p = p.next;
        }
        Node temp = p.next;
        Node data = new Node(o, temp);
        p.next = data;
        size++;
    }

    @Override
    public void add(Object o) throws Exception {
        this.add(size, o);
    }

    @Override
    public Object remove(int i) throws Exception {
        if(i<0 || i>=size) {
            throw new Exception("索引越界");
        }
        Node p = head;
        for(int j=0; j<i; j++) {
            p = p.next;
        }
        Node temp = p.next;
        p.next = temp.next;
        size--;
        return temp.data;
    }

    @Override
    public boolean contains(Object o) {
        Node p = head;
        for(int j=0; j<size; j++) {
            p = p.next;
            if (o.equals(p.data)) {
                return true;
            }
        }
        return false;
    }

    @Override
    public int indexOf(Object o) {
        Node p = head;
        for(int j=0; j<size; j++) {
            p = p.next;
            if (o.equals(p.data)) {
                return j;
            }
        }
        return -1;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        Node p = head;
        for (int i = 0; i < size; i++) {
            p = p.next;
            if (i != size-1) {
                sb.append(p.data + ",");
            }else {
                sb.append(p.data);
            }
        }
        sb.append("]");
        return sb.toString();
    }

}
测试
package com.xgc.linearlist.linkedlist.doublylinkedlist.withheadnodeandtailnode;

import com.xgc.linearlist.LinearListADT;

public class DoublyLinkedListTest {
    public static void main(String[] args) throws Exception {
        LinearListADT list = new DoublyLinkedList();
        System.out.println(list.isEmpty());

        list.add("xgc");
        list.add("xiaoli");
        System.out.println(list);
        System.out.println(list.isEmpty());

        list.remove(1);
        System.out.println(list);

        System.out.println(list.contains("xgc"));

        System.out.println(list.size());

        System.out.println((String)list.get(0));

        System.out.println(list.indexOf("xgc"));

        list.add("zhangsan");
        list.add("xiaoming");
        list.add("xiaohong");
        list.add("lili");
        System.out.println(list);
    }
}

测试结果

true
[xgc,xiaoli]
false
[xgc]
true
1
xgc
0
[xgc,zhangsan,xiaoming,xiaohong,lili]

文章永久链接：https://tech.souyunku.com/40733

AD：【JetBrains 全家桶，激活、破解、教程】获取 IDEA 激活码、PyCharm 激活码、WebStorm 激活码和 DataGrip 激活码，提供详细破解教程与永久激活方法。支持 IDEA 永久激活与破解，免费获取注册码与激活码，解决 2024/2025 版本激活问题，轻松实现所有 JetBrains 工具的激活。
未经允许不得转载：搜云库技术团队 » 线性表以及Java代码实现

相关推荐

热门专题

JetBrains 全家桶，激活、破解、教程

提供 JetBrains 全家桶激活码、注册码、破解补丁下载及详细激活教程，支持 IntelliJ IDEA、PyCharm、WebStorm 等工具的永久激活。无论是破解教程，还是最新激活码，均可免费获得，帮助开发者解决常见激活问题，确保轻松破解并快速使用 JetBrains 软件。获取免费的破解补丁和激活码，快速解决激活难题，全面覆盖 2024/2025 版本！

联系我们联系我们