数据结构-链表

一.ArrayList的缺陷和优点

二.什么是链表

1.链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序表现的

2.链表的结构

链表的结构就像火车,每一节车厢都有一个连接,链表就是由一个个节点组成的.

注意:
1.链表结构在逻辑上连续,在物理上不一定连续.
2.现实中的节点一般都是在堆上申请的.
3.在堆上申请的空间可能连续也可能不连续.

3.链表

链表分为数据域和next域:数据域主要存储数据,next域是指向下一个节点的地址.

4.链表的结构

其实链表的结构有很多,但是这里我们主要学会单向不带头非循环,和双向不带头非循环即可

三.链表的创建

1.链表的创建我们可以通过创建内部类的方式来创建一个节点.

 static class ListNode{
        //数据域
        public int val;
        //next域
        public ListNode next;

        //构造方法:只给数据域,因为不知道节点的next域是谁
        public ListNode(int val){
            this.val=val;
        }

    }

创建一个节点的时候我们要注意在提供构造方法时只需要给一个数据域就可以,因为我们无法知道节点的next域是谁.

2.节点创建好了以后我们应该怎样连起来?

这里我们先用穷举的方式将节点连接起来.
1.首先我们先实例化几个节点
2.通过next将这些节点串联起来
3.由于这里的node1是局部变量,出了方法就会销毁,所以我们可以将node1存储到head中.

 ListNode node1=new ListNode(12);
        ListNode node2=new ListNode(23);
        ListNode node3=new ListNode(34);
        ListNode node4=new ListNode(45);
        ListNode node5=new ListNode(56);

        //通过next串联节点
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;


        this.head=node1;

经历以上的步骤之后,通过测试类调用该创建方法,我们就可以看到节点已经串联起来了.

四.链表的实现

1.遍历整个链表

因为链表不能通过for循环来遍历,所以我们应该采取什么方式来遍历链表

 @Override
    public void display() {
        ListNode cur=head;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
    }
}

这里我们通过next域来遍历链表,让链表可以走到下一个节点.如图,但是一定要注意循环的限制条件.

如果想让cur停在最后一个节点的位置就用cur.next!=null;

如果想把整个链表遍历完,就是cur!=null;

很显然我们这里需要将整个链表遍历完,所以用cur!=null;

注意:这里不能直接用head遍历整个链表,因为用head之后头结点就会发生改变,所以我们最好创建一个新的节点将head给到新节点cur.

2.判断链表是否包含某个元素

1.首先还是要将head赋值给一个新节点.来保证head不被影响

2.我们还是要将整个链表遍历完

3.当节点数据域的值和key相等时候返回true,如果一直不相等,返回false.

3.链表的头插法

1.首先实例化一个节点

2.当链表为空时,插入的第一个节点就是头节点.

  ListNode newH=new ListNode(data);
        if(head==null){
            this.head=newH;

3.如果节点不为空,我们就将头结点的地址给到新节点的next域,并且将新节点给到head,这样新节点就完成了头插.

4.头插法的时间复杂度为O(1).

/*
头插法
    1.先判断是链表是否为空,如果为空插入的第一个节点就是头结点
    2.如果有节点
    先实例化一个节点
    将head给新节点的next
    将新节点给到head
 */

    @Override
    public void addFirst(int data) {
        ListNode newH=new ListNode(data);
        if(head==null){
            this.head=newH;
        }else {
            newH.next=head;
            head=newH;
        }

    }

4.尾插法(指的是将节点放在链表的最后一个位置)

1.和头插法一样先实例化一个节点

2.将头结点给到cur

3.当链表为空时,插入的node节点就是头结点

4.如果链表不为空,就可以让cur通过循环走到最后一个节点

5.将新节点的地址给最后一个节点的next

6.尾插法的时间复杂度为O(N).

5.在任意位置插入一个节点(实现的时候一定要先绑定后面)

1.在任意位置插入一个节点我们必须要知道他的前一个节点才可以插入

//通过方法找到插入位置的前一个节点,返回这个节点.
 private ListNode searchPrev(int index){
        ListNode cur=head;
        while (index-1!=0){
            cur=cur.next;
            index--;
        }
        return cur;
    }

2.我们还要判断index的合法性

在这里插入代码片

  public void IndexAbnormal(int index){
        if(index<0||index>size()){
            throw new IndexAbnormity("Index异常");
        }
    }

 //判断index的合法性
        if(index<0||index>size()){
           try {
                IndexAbnormal(index);
           }catch (IndexAbnormity e){
               e.printStackTrace();
           }
        }

3.当插入位置为0时,就使用头插法

 if(index==0){
            addFirst(data);
            return;
        }

4.当插入位置为最后时,使用尾插法

    if (index==size()){
            addLast(data);
            return;
        }

5.中间位置插入

切记先绑定后边再绑定前面

ListNode cur=searchPrev(index);
        ListNode node=new ListNode(data);
        node.next=cur.next;
        cur.next=node;

6.完整代码

/*
    在任意位置插入一个节点

     */
    @Override
    public void addIndex(int index, int data) {
        //判断index的合法性
        if(index<0||index>size()){
           try {
                IndexAbnormal(index);
           }catch (IndexAbnormity e){
               e.printStackTrace();
           }
        }
        if(index==0){
            addFirst(data);
            return;
        }
        if (index==size()){
            addLast(data);
            return;
        }
        ListNode cur=searchPrev(index);
        ListNode node=new ListNode(data);
        node.next=cur.next;
        cur.next=node;

    }
    private ListNode searchPrev(int index){
        ListNode cur=head;
        while (index-1!=0){
            cur=cur.next;
            index--;
        }
        return cur;
    }
    public void IndexAbnormal(int index){
        if(index<0||index>size()){
            throw new IndexAbnormity("Index异常");
        }
    }

6.删除一个节点

1.当链表为空的时候无法删除

 if (head==null){
            System.out.println("无法删除");
        }

2.删除节点为头结点,直接将头结点指向他的下一个节点

  if (head.val==key){
            this.head=this.head.next;
        }

3.删除中间节点

(1).找到要删除的节点(找到要删除节点的前一个节点)

private ListNode FindPrev(int key){
        ListNode cur =head;
        while (cur.next!=null){
            if(cur.next.val==key){
                return cur;
            }
        }
        return null;
    }

 ListNode cur=FindPrev(key);

(2).判断是不是为空

   if (cur==null){
            System.out.println("没有找到你要的数字");
            return;
        }

(3).定义一个del节点(cur是删除节点前一个节点,通过让cur.next直接指向del.next来达到删除的目的)

 //定义一个del节点
        ListNode del=cur.next;
        cur.next=del.next;