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

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

到此这篇关于Java全面讲解顺序表与链表的使用 的文章就介绍到这了,更多相关Java顺序表与链表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！