欢迎来到代码驿站！

JAVA代码

当前位置：首页 > 软件编程 > JAVA代码

Java全面讲解顺序表与链表的使用

时间：2023-03-09 12:09:19|栏目：JAVA代码|点击： 次

线性表

线性表 （ linear list ） 是 n 个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见 的线性表：顺序表、链表、栈、队列、字符串 ... 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构（内存上）上并不一定是连续的，线性表在物理上存储时，通常以数组（在物理上是连续的）和链式结构（在物理上不连续）的形式存储。

顺序表

顺序表是用一段 物理地址连续 的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。（可以说顺序表就相当于一个数组）

那么问题来了，为什么不直接使用数组，而要把数组放在类当中，然后再对数组进行操作？ 因为数组没有面向对象，把数组放进类当中，可通过对象对它进行操作。

听着概念有点模糊，接下来通过模拟顺序表的接口实现来认识一下顺序表：

?用Arraylist来模拟实现顺序表ArrayList的接口实现：

Arraylist:

public class Arraylist{
    public int[] arr;
    public int useSize;//数组有效个数
    public Arraylist() {
        this.arr = new int[10];//假设数组长度为10
    }
    //打印顺序表
    public void display() {
        for (int i = 0; i < this.useSize; i++) {
            System.out.print(this.arr[i] + " ");
        }
        System.out.println();
    }
    public boolean isFull() {
        return this.arr.length == this.useSize;
    }
    // 在 pos 位置新增元素
    public void add(int pos, int date) {
        if (pos < 0 || pos > useSize) {
            System.out.println("pos位置不合法"+" ");
            return;
        }
        if (isFull()) {
            this.arr = Arrays.copyOf(this.arr, 2 * this.arr.length);
        }
        for (int i = this.useSize - 1; i >= pos; i--) {
            this.arr[i + 1] = this.arr[i];
        }
        this.arr[pos] = date;
        this.useSize++;
    }
    // 判定是否包含某个元素
    public boolean contains(int toFind) {
        for (int i = 0; i < this.useSize; i++) {
            if (arr[i] == toFind) {
                return true;
            }
        }
        return false;
    }
    // 查找某个元素对应的位置
    public int search(int toFind) {
        for (int i = 0; i < this.useSize; i++) {
            if (arr[i] == toFind) {
                return i;
            }
        }
        return -1;
    }
    // 获取 pos 位置的元素
    public int getPos(int pos) {
        if (pos < 0 || pos >=useSize){
            System.out.println("pos位置不合法"+" ");
            return -1;//万一顺序表中有-1这个元素怎么办，后期说
        }
        if(isEmpty()){
            System.out.print("顺序表为空");
            return -1;
        }
        for (int i = 0; i < this.useSize; i++) {
            if (i == pos) {
                return this.arr[i];
            }
        }
        return -1;
    }
    public boolean isEmpty(){
        return this.useSize==0;
    }
    // 给 pos 位置的元素设为 value
    public void setPos(int pos, int value) {
        if (pos < 0 || pos >=useSize){
            System.out.print("pos位置不合法"+" ");
            return;
        }
        if(isEmpty()){
            System.out.println("顺序表为空");
            return;
        }
                this.arr[pos] = value;
    }
    //删除第一次出现的关键字key
    public void remove(int toRemove){
        if(isEmpty()) {//判断顺序表是否为空
            System.out.println("顺序表为空");
        }
        int x=search(toRemove);
        if(x==-1){
            System.out.println("没有你要删除的数字");
            return;
        }
                for (int j = x; j<=this.useSize-1; j++) {
                    this.arr[j]=this.arr[j+1];
                }
        this.useSize--;
    }
    //清空顺序表
    public void clear() {
        this.usedSize = 0;
  }
}

在pos位置新增元素：

判断是否包含某个元素：

查找pos位置：

在pos位置上给值value

删除第一次出现的关键字key

链表

链表是一种 物理存储结构(内存）上非连续 存储结构，数据元素的 逻辑顺序 是通过链表中的 引用链接 次序实现的 。 实际中链表的结构非常多样，以下情况组合起来就有 8 种链表结构：

单向、双向

带头、不带头

循环、非循环

接下来主要讲两种：单向不带头非循环、双向不带头非循环

?链表接口的模拟实现（ 单向不带头非循环）： 链表是由一个一个节点组成，单向不带头非循环链表每个节点有两个域，一个是数据域，用来存放数据，另一个是存放下一个节点的地址。

class ListNode{//创建节点,链表是由一个一个节点组成，每个节点有两个域组成，数据域和下一个节点地址组成
     public int val;
     public ListNode next;//没有初始化默认为null
     public ListNode(int val){
         this.val=val;
     }
}
//模拟实现单向不带头非循环链表的接口实现，用MyLinkedList模拟实现LinkedList
public class MyLinkedList {
    public ListNode head;//创建头节点
    public void createList() {
        ListNode listNode1 = new ListNode(12);
        ListNode listNode2 = new ListNode(88);
        ListNode listNode3 = new ListNode(36);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        this.head = listNode1;//头节点为第一个节点地址
    }
    public void display() {
        ListNode cur;
        cur = this.head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    //头插法
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
    }
    //尾插法
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        ListNode cur = this.head;
        if (cur == null) {
            this.head = node;
        } else {
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
    }
    //找到index-1下标位置
    public ListNode findIndex(int index) {
        ListNode cur = this.head;
        while (index - 1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }
//任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index, int data) {
        if(index<0||index>size()){
            System.out.println("输入位置不合法");
            return;
        }
        if(index==0){//头插
            this.addFirst(data);
            return;
        }
        if(index==size()){//尾插
            this.addLast(data);
            return;
        }
            ListNode cur = findIndex(index);
            ListNode node = new ListNode(data);
            node.next = cur.next;
            cur.next = node;
    }
    public boolean contains(int key) {
        return false;
    }
    public ListNode findremove(int key){
    ListNode cur=this.head.next;
    while(cur!=null) {
        if (cur.next.val == key) {
            return cur;
        } else {
            cur=cur.next;
        }
    }
    return null;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        if (this.head == null) {
            System.out.println("链表为空");
            return;
        }
        if (this.head.val == key) {
            this.head = this.head.next;
            return;
        }
        ListNode cur = findremove(key);//找到关键字上一个节点所在位置，并返回该节点
        if (cur == null) {
            System.out.println("没找到关键字");
            return;
        }
            ListNode del=cur.next;
            cur.next=del.next;
        return;
    }
    //删除所有值为key的节点
    public ListNode removeAllKey(int key) {
        if(this.head==null){
            return null;
        }
        ListNode per=this.head;
        ListNode cur=this.head.next;
        while(cur!=null){
            if(cur.val==key){
                per.next=cur.next;
                cur=cur.next;
            }
            else{
                per=cur;
                cur=cur.next;
            }
        }
        if(this.head.val==key){
            this.head=this.head.next;
        }
        return this.head;
    }
    //得到单链表的长度
    public int size() {
        ListNode cur=this.head;
        int count=0;
        while (cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
   //清除链表
    public void clear() {
        //this.head=null;//简单粗暴写法，当一个节点没有被指向时，就没意义了
       //遍历
        while(this.head!=null){
         ListNode curNext=this.head.next;
         this.head.next=null;
         this.head=curNext;
        }
    }
}

创建节点：

以上说的链表是指单向不带头非循环链表！！！

初始化链表：

打印链表：

头插法：

尾插法：

任意位置插入一个数据：

删除关键字key所在节点位置：

删除所有值为key的节点：

双向不带头非循环：

这种链表至少有三个域组成，一个是数据域，一个是存放上一个节点的位置，一个存放下一个节点的位置，双向比单向的好处就体现出来了，双向链表只要知道当前节点位置，就可以对链表进行增删查改，而单相链表还需要知道当前节点的上一个节点。

接口模拟实现：

//双向不带头非循环
//创建节点
class ListNode{
    int val;
    ListNode prev;//前一个节点地址
    ListNode next;//下一个节点地址
    public ListNode(int val){
        this.val=val;
    }
        }
public class myLinkedList {
    public ListNode head;//头节点
    public ListNode last;//尾节点
 
    //得到双向链表长度
    public int size() {
        int count = 0;
        ListNode cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;//如果链表为空。返回0，所以这里可再单独判断也可不单独判断
    }
 
    //打印双向链表
    public void display() {
        ListNode cur = this.head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
 
    //查找是否包含关键字在链表中
    public boolean contain(int key) {
        if (this.head == null) {
            return false;
        }
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
                cur = cur.next;
        }
        return false;
    }
 
    //删除第一次出现的关键字
    public void remove(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                if (cur == head) {//第一种：关键字是在头节点
                    this.head = this.head.next;
                    if (this.head != null) {
                        head.prev = null;
                    } else {//如果链表为空1情况下，要保证最后一个节点也要为空
                        this.last = null;
                    }
                } else {//第二种情况：关键字在中间或者结尾
                    cur.prev.next = cur.next;
                    if (cur.next != null) {//中间
                        cur.next.prev = cur.prev;
                    } else {
                        last = cur.prev;//结尾
                    }
                }
                return;
            }
            cur=cur.next;
        }
    }
 
    //删除所有值为key的节点
    public void removeAllkey(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                if (cur == head) {//第一种：关键字是在头节点
                    this.head = cur.next;
                    if (this.head != null) {
                        cur.next.prev = null;
                    } else {//如果链表为空1情况下，要保证最后一个节点也要为空
                        this.last = null;
                    }
                } else {//第二种情况：关键字在中间或者结尾
                    cur.prev.next = cur.next;
                    if (cur.next!=null) {//中间
                        cur.next.prev = cur.prev;
                    }
                    last = cur.prev;//结尾
                }
            }
            cur=cur.next;
        }
    }
 
    //头插法
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        if (this.head == null) {
            this.head = node;
            this.last = node;
        }
        else {
            node.next = this.head;
            this.head.prev = node;
            this.head = node;
        }
    }
    //尾插法
    public void addLast(int data){
        ListNode node=new ListNode(data);
        if(this.head==null) {
            this.head = node;
            this.last = node;
        }
        this.last.next=node;
        node.prev=this.last;
        this.last=node;
    }
    //任意位置插入，第一个数据节点下标为0
    public ListNode search(int index){//寻找插入的位置
      ListNode cur=this.head;
      while(index!=0){
          cur=cur.next;
          index--;
      }
      return cur;
    }
    public void addIndex(int index,int data){
        ListNode node=new ListNode(data);
        if(index<0||index>size()){
            System.out.println("坐标违法");
            return;
        }
        if(index==0){
            addFirst(data);
            return;
        }
        if(index==size()){
            addLast(data);
            return;
        }
 
        ListNode cur=search(index);
        node.next=cur.prev.next;
        cur.prev.next=node;
        node.prev=cur.prev;
        cur.prev=node;
        return;
    }
    //清除链表
    public void clear(){
        while(this.head!=null){
            ListNode curNext=this.head.next;
            this.head.prev=null;
            this.head.next=null;
            this.head=curNext;
        }
        last=null;
    }
}

查找是否包含关键字在链表中：

删除第一次出现的关键字：

删除所有值为key的节点：

头插法：

尾插法：

任意位置插入，第一个数据节点下标为0：

小结

在这里，我们讲了顺序表也讲了链表，那么他们有什么区别呢？

在组织上：

1、顺序表底层是一个数组，他是一个逻辑上和物理上都是连续的

2、链表是一个由若干节点组成的一个数据结构，逻辑上是连续的但是在物理上[内存上]是不连续的。

在操作上：

1、顺序表适合，查找相关的操作，因为，可以使用下标，直接获取到某个位置的元素。

2、链表适合于,频繁的插入和删除操作。此时不需要像顺序表一样,移动元素。链表的插入只需要修改指向即可。

3、顺序表还有不好的地方，就是你需要看满不满，满了要扩容，扩容了之后，不一定都能放完。所以，他的空间上的利用率不高。

以上就是我对顺序表和链表的一些理解，如果有什么不对的地方，欢迎各位提出来！

上一篇：解决mybatis使用foreach批量insert异常的问题

栏    目：JAVA代码

下一篇：解析rainbond以应用为中心的架构设计原理

本文标题：Java全面讲解顺序表与链表的使用

本文地址：http://www.codeinn.net/misctech/227115.html

更多JAVA代码

阅读排行

推荐教程

广告投放 | 联系我们 | 版权申明

重要申明：本站所有的文章、图片、评论等，均由网友发表或上传并维护或收集自网络，属个人行为，与本站立场无关。

如果侵犯了您的权利，请与我们联系，我们将在24小时内进行处理、任何非本站因素导致的法律后果，本站均不负任何责任。

联系QQ：914707363 | 邮箱：codeinn#126.com(#换成@)

Copyright © 2020 代码驿站 版权所有