初识顺序表和链表

发布时间：2024-02-22 15:00

\"初识顺序表和链表_第1张图片\"

 

目录

线性表

顺序表

链表

小结

线性表

线性表 （ 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位置新增元素：

\"初识顺序表和链表_第2张图片\"

 \"初识顺序表和链表_第3张图片\"

 判断是否包含某个元素：

\"初识顺序表和链表_第4张图片\"

 查找pos位置：

\"初识顺序表和链表_第5张图片\"

 在pos位置上给值value

\"初识顺序表和链表_第6张图片\"

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

\"初识顺序表和链表_第7张图片\"

链表

链表是一种 物理存储结构(内存）上非连续 存储结构，数据元素的 逻辑顺序 是通过链表中的 引用链接 次序实现的 。
实际中链表的结构非常多样，以下情况组合起来就有 8 种链表结构：
单向、双向
带头、不带头
循环、非循环
\"初识顺序表和链表_第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;
        }
    }
}

创建节点：

\"初识顺序表和链表_第9张图片\"

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

初始化链表：

\"初识顺序表和链表_第10张图片\"

 打印链表：

\"初识顺序表和链表_第11张图片\"

 头插法：

\"初识顺序表和链表_第12张图片\"

尾插法：

\"初识顺序表和链表_第13张图片\"

 任意位置插入一个数据：

\"初识顺序表和链表_第14张图片\"

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

\"初识顺序表和链表_第15张图片\"

 删除所有值为key的节点：

\"初识顺序表和链表_第16张图片\"

双向不带头非循环：

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

\"初识顺序表和链表_第17张图片\"

 接口模拟实现：

//双向不带头非循环
//创建节点
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;
    }
}

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

\"初识顺序表和链表_第18张图片\"

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

\"初识顺序表和链表_第19张图片\"

 删除所有值为key的节点：

\"初识顺序表和链表_第20张图片\"

 

头插法：

\"初识顺序表和链表_第21张图片\"

 尾插法：

\"初识顺序表和链表_第22张图片\"

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

\"初识顺序表和链表_第23张图片\"

 小结

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

在组织上：

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

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

在操作上：

1、顺序表适合，查找相关的操作，因为，可以使用下标，直接获取到某个位置的元素。
2、链表适合于,频繁的插入和删除操作。此时不需要像顺序表一样,移动元素。链表的插入只需要修改指向即可。
3、顺序表还有不好的地方，就是你需要看满不满，满了要扩容，扩容了之后，不一定都能放完。所以，他的空间上的利用率不高。

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

\"初识顺序表和链表_第24张图片\"

 

\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0

相关推荐

超级简单的jquery轮播图demo

Kubernetes（k8s）入门及集群部署文档

MYSQL---索引---B+树

C语言指针，这可能是史上最干最全的讲解啦（附代码）！！！

DS图—图的连通分量 答案

python中TKinter组件的使用

数学建模学习（74）：隔离森林的异常值查找，简单的学会

ROS+UR机械臂系列-1- 虚拟机及ROS安装

SpringCloud微服务全家桶

鸿蒙APP开发学习-HarmonyOS（1）

Python分布式爬虫打造搜索引擎完整版-基于Scrapy、Redis、elasticsearch和django打造一个完整的搜索引擎网站

HTML和CSS、JavaScript规范 第一部分（CSS部分）

Java基础高级——常用类总结

hcip--第三天随堂作业

SpringBoot+Thymeleaf+ECharts实现大数据可视化(基础篇)

NFT深度分析：属性、历程、平台、营销模式、场景等

web安全攻击方法流量分析

torchvision 中 deform_conv2d 操作的经验性解析

deeplabv3+系列之deeplabv3网络搭建

普渡大学计算机图形,美国：普渡大学（UX方向）

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网，如有侵权请联系：561261067@qq.com

桂ICP备16001015号