亲宝软件园·资讯

展开

Java顺序表和链表

ᝰꫛꪮꪮꫜ* 人气:0

前言:

线性表(linear list)是n个具有相同特性的数据元素的有限序列。

线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串。

顺序表

定义:

用一段物理地址连续的存储单元依次存储数据元素的线性结构(逻辑上连续,物理上也连续)

(1)静态顺序表:使用定长数组存储。

(2)动态顺序表:使用动态开辟的数组存储

【注意】静态顺序表的定长数组导致N定大了,空间开多了浪费,开少了不够用,所以相比之下,动态数组更为灵活,可根据需要动态分配空间大小

实现方法:

增、删、改、查

增加操作:从头部插入、从尾部插入、在任意索引位置处插入

删除操作:根据索引删除元素、根据元素值删除第一个出现的该元素、根据元素值删除所有该值元素 

查找操作:根据元素值查找是否存在某元素、根据索引下标返回该处元素值、根据元素值返回索引下标 

修改操作:根据索引下标修改该处元素 

代码实现:

public class MyArray {
    private int[]data;
    private int size;
//    无参构造
    public MyArray(){
        this.data=new int[5];
    }
//    有参构造
    public MyArray(int n){
        this.data=new int[n];
    }
//    grow方法用于扩充内存
    private void grow() {
        int[] newdata= Arrays.copyOf(data,size*2);
        this.data=newdata;
    }
//    toString方法输出顺序表内容
    public String toString(){
        String str="[";
        for (int i = 0; i <size ; i++) {
            str+=data[i];
            if(i!=size-1){
            str+=",";
            }
        }
        str+="]";
        return str;
    }
//    尾插法:
    public void addLast(int value){
        if(size== data.length){
            grow();
        }
        data[size]=value;
        size++;
    }
//    头插法:
    public void addFirst(int value){
        if(size==data.length){
            grow();
        }
        for (int i = size-1; i >=0; i--) {
            data[i+1]=data[i];
        }
        data[0]=value;
        size++;
    }
//    中间任意位置插入:
    public void addIndex(int index,int value){
        if(size==data.length)
            grow();
        if(index<0||index>size){
            System.err.println("插入位置不合理!");
            return;
        }
        else {
            for (int i = size - 1; i >= index; i--) {
                data[i + 1] = data[i];
            }
            data[index] = value;
            size++;
        }
    }
//    查看当前数组中是否存在该元素
    public boolean contains(int value){
        for (int i = 0; i < size; i++) {
            if(data[i]==value)
                return true;
        }
        return false;
    }
//    查找当前数组元素对应的下标
    public int getIndex(int value){
        for (int i = 0; i < size; i++) {
            if(data[i]==value){
                return i;
            }
        }
        return -1;
 
    }
//    查找数组下标为index的元素
    public int getValue(int index) {
        if (index < 0 || index > size - 1) {
            System.out.println("输入下标不合理");
            return -1;
        }
 
        return data[index];
    }
//    根据索引删除元素,注意将最后一个元素置为0
    public void removeIndex(int index){
        if(index<0||index>=size){
            System.err.println("输入不合法!");
        }
        for (int i = index; i <size-1; i++) {
            data[i]=data[i+1];
        }
        size--;
        data[size]=0;
    }
//    删除第一个元素值为value的元素
    public void removeValueOnce(int value){
        int a=getIndex(value);
      removeIndex(a);
 
        }
//        删除所有元素值为value的元素
    public void removeValueAll(int value){
        for (int i = 0; i < size; i++) {
           while(i!=size||data[i]==value)
               removeIndex(i);
 
        }
 
    }
//    根据索引修改元素
    public void recompose(int index,int newValue){
        if(index<0||index>=size){
            System.err.println("输入不合法!");
        }
 
        data[index]=newValue;
    }
    }

链表

定义:

逻辑上连续,物理上非连续存储。

链表由一个个节点组成,每个节点存储该节点处的元素值val 以及下一个节点的地址next,由地址next实现逻辑上连续

分类:

分类方式:

(1)单链表、双链表

(2)带虚拟头节点、不带虚拟头节点

(3)循环链表、非循环链表

按不同分类方式组合有8种:

非循环四种:

(1)不带虚拟头节点的单向链表(非循环)

(2)带虚拟头节点的单向链表(非循环)

(3)不带虚拟头节点的双向链表(非循环)

(4)带虚拟头节点的双向链表(非循环)

循环四种:

(5)不带虚拟头节点的单向链表(循环)

(6)带虚拟头节点的单向链表(循环)

(7)不带虚拟头节点的双向链表(循环)

(8)带虚拟头节点的双向链表(循环)

其中:

(1)不带虚拟头节点的单向链表(非循环):结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。这种结构在笔试面试中出现很多

(7)不带虚拟头节点的双向链表(循环):在Java的集合框架库中LinkedList底层实现就是无头双向循环链表

实现方法:

增、删、查、改     和顺序表实现方法基本一样;

唯一注意:带虚拟头节点与不带虚拟头节点相比,带虚拟头节点避免了考虑头节点为空的特殊情况

代码实现:

(1)不带虚拟头节点的单链表:

class Node {
//    val表示存储的数值,next表示下一个节点的地址
    int val;
    Node next;
 
    //    构造方法
    public Node(int val) {
        this.val = val;
    }
}
 
public class SingleList {
    //    size表示节点个数
//    head表示头节点
    private int size;
    private Node head;
 
    //定义toString方法以输出链表内容
    public String toString() {
        String str = "";
        Node node = head;
        while (node != null) {
            str += node.val;
            str += "->";
            node = node.next;
        }
        str += null;
        return str;
    }
 
    //将判断输入的索引是否合法抽象为方法islegal
    public boolean islegal(int index) {
        if (index < 0 || index > size) {
            return false;
        } else {
            return true;
        }
    }
 
    //    头插法
    public void addHead(int value) {
        Node node = new Node(value);
        if (head == null) {
            head = node;
 
        } else {
            node.next = head;
            head = node;
        }
        size++;
    }
 
    //    中间任意位置插入
    public void addIndex(int index, int val) {
        if (!islegal(index)) {
            System.out.println("输入数据不合法!");
            return;
        }
        if (index == 0) {
            addHead(val);
            return;
        }
        Node node = new Node(val);
        Node pre = head;
 
        for (int i = 0; i < index - 1; i++) {
            pre = pre.next;
        }
        node.next = pre.next;
        pre.next = node;
        size++;
        return;
    }
 
    //    尾插法
    public void addLast(int val) {
        if (head == null) {
            addHead(val);
        } else {
            addIndex(size, val);
        }
    }
 
    //    删除指定索引位置的元素
    public void removeIndex(int index) {
 
        if (islegal(index)) {
            if (index == 0) {
                Node temp = head;
                head = head.next;
                temp.next = null;
                size--;
                return;
            } else {
 
                Node pre = head;
                for (int i = 0; i < index - 1; i++) {
                    pre = pre.next;
                }
                Node cur = pre.next;
                pre.next = cur.next;
                cur.next = null;
 
                size--;
            }
 
        } else {
            System.out.println("输入数据不合法!");
        }
    }
 
    //    根据元素值删除元素,且只删除第一次出现的该元素
    public void removeValueOnce(int val) {
        if (head.next != null && head.val == val) {
            removeIndex(0);
        } else {
            Node pre = head;
            while (pre.next != null) {
                if (pre.next.val == val) {
                    pre.next = pre.next.next;
                    pre.next.next = null;
                    size--;
                    return;
 
                }
                pre = pre.next;
            }
        }
    }
 
    //    根据元素值删除元素,且删除所有该元素
    public void removeValueAll(int val) {
        while (head.next != null && head.val == val) {
            Node temp = head;
            head = head.next;
            temp = null;
            size--;
        }
        if (head == null) {
            return;
        } else {
            Node pre = head;
            while (pre.next != null) {
                if (pre.next.val == val) {
                    pre.next = pre.next.next;
                    size--;
                    return;
 
                } else {
                    pre = pre.next;
                }
            }
        }
    }
 
    //       根据元素值删除元素,且删除所有该元素并返回头节点(带虚假节点)
    public Node removeValueAllWithDummy(int val) {
        Node dummyHead = new Node(-1);
        dummyHead.next = head;
        Node pre = dummyHead;
        while (pre.next != null) {
            if (pre.next.val == val) {
                Node cur = pre.next;
                pre.next = cur.next;
                cur.next = null;
                size--;
            } else {
                pre = pre.next;
            }
        }
        return dummyHead.next;
 
    }
 
    //    根据索引查元素值
    public int get(int index) {
        if (islegal(index)) {
            Node cur = head;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            return cur.val;
        } else {
            System.out.println("输入数据不合法!");
            return -1;
        }
    }
 
    //    能否查到给定的某元素值(自己写的,好像很复杂)
    public boolean contains(int val) {
        boolean a = false;
        if (head == null) {
            System.out.println("该链表为空!");
            return false;
        } else {
            Node node = head;
 
            for (int i = 0; i < size; i++) {
                if (node.val == val) {
                    a = true;
                }
                node = node.next;
            }
        }
        return a;
    }
 
    //    能否查到给定的某元素值,老师写的方法
    public boolean contains2(int val) {
        for (Node temp = head; temp != null; temp = temp.next) {
            if (temp.val == val) {
                return true;
            }
        }
        return false;
    }
 
    //    根据索引修改元素值
    public void set(int index, int newValue) {
        if (islegal(index)) {
            Node node = head;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            node.val = newValue;
            return;
        }
        System.out.println("输入数据不合法!");
    }
}

(2)带虚拟头节点的单链表

以在指定索引位置插入元素为例,理解虚拟头节点的作用即可

public class SingleListWithDummyHead {
    Node dummyNode=new Node(-1);
    int size;
//    在指定位置插入元素,因为有虚拟头节点故不用考虑index=0的情况,全部为在中间位置插入的情况
    public void addIndex(int index,int value){
//        先判断index是否合法
        if(index<0||index>size){
            System.out.println("illegal");
            return;
        }
        Node a=new Node(value);
        Node pre=dummyNode;
        for(int i=0;i<index;i++){
            pre=pre.next;
        }
        a.next=pre.next;
        pre.next=a;
        size++;
    }
}

(3)带虚拟头节点的双链表

public class DoubleLinkedList {
    private int size;
    private Node dummyHead = new Node(-1);
    private Node tail;
 
    //    定义toString方法用以方便输出
    public String toString() {
        String s = "";
        Node node = dummyHead.next;
        while (node != null) {
            s = s + node.val;
            s = s + "->";
            node = node.next;
        }
        s += "null";
        return s;
    }
 
    //    判断输入的索引是否合法
    private boolean isRange(int index) {
        if (index < 0 || index >= size) {
            System.out.println("输入不合法!");
            return false;
        } else
            return true;
    }
 
    //    头插法
    public void addHead(int val) {
        Node a = new Node(val, dummyHead, dummyHead.next);
//链表为空
        if (dummyHead.next == null) {
            tail = a;
            dummyHead.next = a;
        }
//        否则链表不为空
        else {
            dummyHead.next.prev = a;
            dummyHead.next = a;
        }
        size++;
    }
 
    //    尾插法
    public void addTail(int val) {
        Node a = new Node(val, tail, null);
//        链表为空
        if (dummyHead.next == null) {
            dummyHead.next = a;
        }
//        链表不为空
        else {
            tail.next = a;
        }
        tail = a;
        size++;
    }
 
    //    中间位置插入
    public void addMiddle(int index, int val) {
//      判断插入位置合理否
        if (index < 0 || index > size) {
            System.out.println("输入不合法!");
        }
//        头部插入
        else if (index == 0) {
            addHead(val);
        }
//        尾部插入
        else if (index == size) {
            addTail(val);
        }
//        中间任意位置插入
        else {
//先找到要插入位置的前一个元素,可另一个方法找该元素
            Node a = new Node(val, find(index), find(index).next);
            find(index).next.prev = a;
            find(index).next = a;
            size++;
        }
    }
 
    //    这里find的方法是找到index位置的前一个节点元素
    public Node find(int index) {
        Node f = dummyHead;
        for (int i = 0; i < index; i++) {
            f = f.next;
        }
        return f;
 
    }
 
    //    根据索引删除指定位置的元素
    public void removeIndex(int index) {
        if (index < 0 || index >= size) {
            System.out.println("输入不合法!");
            return;
        } else {
            find(index).next.next.prev = find(index);
            find(index).next = find(index).next.next;
            size--;
        }
    }
 
    //    删除指定节点
    private void deleteNode(Node node) {
//        分治思想,先处理node与左边节点,再处理node与右边节点
        Node pre = node.prev;
        Node next = node.next;
//        处理左边,因为有虚拟头节点,故不用另讨论为头节点的情况
        pre.next = next;
        node.prev = null;
//       处理右边
        if (next == null) {
            tail = pre;
        } else {
            next.prev = pre;
            node.next = null;
        }
        size--;
 
    }
 
    //    删除指定元素值(只删除第一次出现的)
    public void removeValueOnce(int val) {
        for (Node a = dummyHead.next; a != null; a = a.next) {
            if (a.val == val) {
                deleteNode(a);
                return;
            }
        }
        System.out.println("链表中无该元素故无法删除");
 
    }
 
    public void removeValueAll(int val) {
        for (Node a = dummyHead.next; a != null; ) {
            if (a.val == val) {
                Node b = a.next;
                deleteNode(a);
                a = b;
            } else a = a.next;
        }
    }
 
    //    根据索引查找元素值
    public int get(int index) {
        if (isRange(index)) {
            return find(index).next.val;
        } else {
            return -1;
        }
    }
 
    //    查找是否存在某元素
    public boolean contains(int val) {
        Node a = dummyHead;
        while (a.next != null) {
            if (a.next.val == val) {
                return true;
            }
            a = a.next;
        }
        return false;
    }
 
    //    修改,将指定位置元素修改为另一值
    public void set(int index, int newValue) {
        if (isRange(index)) {
            find(index).next.val = newValue;
        }
 
    }
 
 
}
 
//节点类
class Node {
    int val;
    Node prev;
    Node next;
 
    public Node(int val) {
        this.val = val;
    }
 
    public Node(int val, Node prev, Node next) {
        this.val = val;
        this.prev = prev;
        this.next = next;
    }
}
 

顺序表 & 链表

顺序表:

优点:空间连续、支持随机访问

缺点:中间或前面部分的插入删除时间复杂度O(N)

           增容的代价比较大。

链表:

优点:任意位置插入删除时间复杂度为O(1)

           没有增容问题,插入一个开辟一个空间 

缺点:以节点为单位存储,不支持随机访问

总结

加载全部内容

相关教程
猜你喜欢
用户评论