请选择 进入手机版 | 继续访问电脑版

#楼主# 2020-3-30

跳转到指定楼层
链表是什么

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(Node)(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域(data),另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间。

线性表的链式存储——算法与数据结构-1.jpg


链表的分类

单链表单向循环链表双向链表双向循环链表


线性表的链式存储结构

头节点和头指针

1、头节点指的是链表中的第一个节点,有真实头节点和虚拟头节点。
1.1 真实头节点:

线性表的链式存储——算法与数据结构-2.jpg

真实头节点的第一个节点存有数据
1.2 虚拟头节点

线性表的链式存储——算法与数据结构-3.jpg

虚拟头节点的第一个节点不能存放数据
2、头指针:存放头节点的地址

插入元素(头插法)

头插法就是在虚拟头节点的后一个插入新的元素,每次插入的新元素,都在最前面,最开始虚拟头节点的next指向为NULL。

线性表的链式存储——算法与数据结构-4.jpg

当有新的元素进来时,它的指针域将会给新节点的指针域指向一下个。而虚拟头节点的指针域则指向新元素的数据域地址。同时rear(尾指针)指向新插入的元素。

线性表的链式存储——算法与数据结构-5.jpg

再插入一个元素B,首先封装成Node节点,然后头节点的next给B的next指向A,然后头节点next再指向新元素。

线性表的链式存储——算法与数据结构-6.jpg

可以看出rear(尾指针)依旧指向最开始进来的元素A,所以可知,第一个头插法进来的元素绝对是尾指针。 它指向的元素是尾节点。


插入元素(尾插法)

尾插法就是在元素的后面插入一个新元素,然后上一节点的指针域指向新元素,同时新元素的指针域指向下一个元素。

线性表的链式存储——算法与数据结构-7.jpg

线性表的链式存储——算法与数据结构-8.jpg

头插尾插结合

当插入第一个元素A时,进行头插法,头节点的next指向元素A,A的next指向下一个,同时rear指向A。当插入B元素时,头插,B的next指向A,头节点指向B的地址。插入C是采取尾插,A的next给C的next。同时A的next指向C。rear(尾指针)指向C。头插法插入D时,D的next指向B,头节点的next指向D。

线性表的链式存储——算法与数据结构-9.jpg

一般插入

如图:在B和A之间插入元素C

线性表的链式存储——算法与数据结构-10.jpg


删除元素(头删)

线性表的链式存储——算法与数据结构-11.jpg

如图:若果想要删除A元素,那么可以让头节点的指针域指向B,但是A的指针域此时也指向B,所以要真正删除A元素,还需要让的指针域指向NULL。

线性表的链式存储——算法与数据结构-12.jpg

线性表的链式存储——算法与数据结构-13.jpg

假设此时只有A一个元素,想要删除掉他的话,头指针和尾指针会怎么变化呢?

线性表的链式存储——算法与数据结构-14.jpg

图中可以看出链表中有两个节点一个元素A。如果要删除A的话,head的next指向为空,然后将rear(尾指针重置为0的状态即谁也不指,则已删除元素A)

线性表的链式存储——算法与数据结构-15.jpg

删除元素(尾删)

现在有三个元素A,B,C,对他们依次进行尾删。

线性表的链式存储——算法与数据结构-16.jpg

首先删除A元素(size-1),我们可以先将尾指针rear指向C,然后将C的next指向NULL,来删除A,删除C时,将rear指向B,B的next指向NULL,删除B时,rear指向虚拟头节点,然后头节点的next指向NULL。

线性表的链式存储——算法与数据结构-17.jpg

删除元素(一般删除)

线性表的链式存储——算法与数据结构-18.jpg

在上面三个元素,四个节点中删除C元素,首先要找到C元素的位置,找到之后,让B的next指向A,同时将C的next置为NULL,这样就可以删除C元素了。

线性表的链式存储——算法与数据结构-19.jpg


LinkedList实现的也是List接口,所以它得实现List中的方法。

其中,需要有一个Node类作为内部类,来对元素进行封装,包含它的数据域(data),指针域(next)
private class Node{
        E data; //数据域
        Node next;  //指针域
        public Node(){
            this(null,null);
        }
        public Node(E data,Node next){
            this.data = data;
            this.next = next;
        }

        @Override
        public String toString() {
            return data.toString();
        }
    }
定义三个变量,head指的是头指针,rear是尾指针,size是其中元素的个数,创建一个无参的构造方法,初始化一个节点,包括它的虚拟头节点,它的尾指针和头指针指向同一个节点对象,此时里面的元素为0
public class LinkedList implements List {
//内部类Node,结点信息
    private class Node{
        E data; //数据域
        Node next;  //指针域
        public Node(){
            this(null,null);
        }
        public Node(E data,Node next){
            this.data = data;
            this.next = next;
        }

        @Override
        public String toString() {
            return data.toString();
        }
    }
\t
\tprivate Node head;  //指向头结点的头指针
    private Node rear;  //指向尾结点的尾指针
    private int size;   //记录元素的个数

\tpublic LinkedList(){
        head = new Node();
        rear = head;
        size=0;
    }

    public LinkedList(E[] arr){
        head = new Node();
        rear = head;
        size =0;
    }

}

getSize()


获取链表中的元素个数,可以借助Arrays中的getSize()方法。因为链表也是线性表的一种。
@Override
    public int getSize() {
        return size;
    }
isEmpty()


链表为空时,它的next指向为NULL,同时里面的元素个数为0,所以它的判空条件size=0,head.next=null即如图:

线性表的链式存储——算法与数据结构-20.jpg

\t@Override
    public boolean isEmpty() {
        return size==0&&head.next==null;
    }
add(int index,E e)


首先要对index的位置进行判断是否合法,然后看是头插还是尾插或者是一般插入,当是头插法的时候,将head的next给插入节点的next然后在让head指向node。当元素个数为0的时候,让尾指针指向新的元素。
public void add(int index, E e) {
        if(indexsize){
            throw new IllegalArgumentException("插入角标非法!");
        }
        //头插
        Node node = new Node(e, null);
        if(index==0){
            node.next = head.next;
            head.next = node;
           rear.next = node;
        }if(size==0){
        \trear = node;
        }

当插入元素是最后一个,则采用尾插法rear.next指向新插入的元素,然后尾指针后移
else if(index==size){
\trear.next = node;
\trear = rear.next;
}
当使用一般插入的时候,首先你要找到你要插入位置的前驱的节点。找到它之后,将它的next给插入的元素然后指向下一个元素,再让它的前驱节点和它连接在一起。
else{
\tNode p = head;
\tfor(int i=0;i
转播转播 分享淘帖
回复

使用道具

成为第一个回答人

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则