链表

链表

一：单向链表

 链表是一个一个元素的添加的

 

每一个节点都是用到时 才会进行分配内存空间

 由于动态数组和链表中  接口方法是相同的但是实现的代码是不一样的

因此我们定义一个接口List

实现这个接口的每一个类都应该实现这个接口中的所有方法

 插播一条Java语法的问题：

我们的动态数组ArrayList和链表linkedList都是实现于List的

因此我们可以用类似于多态的形式进行new

 接口设计：

 

clear：

next不需要设置为null

因为当size==0时  第一个节点消失死亡 跟着的后面节点一个一个也跟着死亡消失 

add:

步骤：找到要添加到位置的前一个元素

让添加的元素的next指向1处的22

让0处的next指向添加元素的44 

1. 找到对应索引下标的节点node

 2.获取某个节点处的元素值

 3.add

先找到要添加位置的前一个位置

之后再进行new出来一个新的节点

但是如果增加到0下标处时

我们需要改正  改正如下：

我们需要让头节点的指向也就是这里的first指向重新定义

 

如果增加到最后一个位置时  但是这种情况可以被第二种添加方式所包含

 

 删除：

 获取前面一个元素  

让前面一个next的指向  指向下一个位置

 这里的first也就是链表头节点的first

 练习题1：

 

思路：

1.首先用要被删除元素的元素的值进行覆盖 node.val=node.next.val;

2.再用要被删除元素的前一个结点的next指向node.next.next

node.next=node.next.next;

 

练习题2：

反转：

方法一：递归方法

举个例子：
当我们函数传参传递的是4时 那么反转之后的链表形式如图 ：

 

 

 

 

 习题3：

package 链表动态数组.链表.单链表;

import 链表动态数组.链表.双向链表.双向链表;

public class linkedList extends 双向链表{
    
    public void clear(){
        size=0;         
        first=null;
    }
    
    public int size() {
        return size;
    }
    
    public boolean isEmpty(){
        return size==0;
    }
    
    public boolean contains(E elements){
        双向链表.Node node=first;
        for (int i = 0; i < size; i++) {
            if(node.element==elements){
                return true;
            }
            node=node.next;
        }
        return false;
    }
    
    public void add(int index,E element) {
        if(index==0){
            first=new 双向链表.Node<>(element,first);
        } else {
            双向链表.Node prev=node(index-1);
            prev.next=new 双向链表.Node<>(element,prev.next);
        }
        size++;
    }

    
    private 双向链表.Node node(int index){
        双向链表.Node node=first;
        for (int i = 0; i  node=node(index);
        E old=node.element;
        node.element=element;
        return old;//返回原来的元素值
    }
 
    
    public E remove(int index){
        双向链表.Node node=first;
        if(index==0){
            first=first.next;
        } else {
            双向链表.Node prev=node(index-1);//找到前驱
            node=prev.next;//对node重新赋值哦
            prev.next=node.next;//进行删除
        }
        size--;
        return node.element;//把这个被删除的节点的元素值进行返回
    }
    
    public int indexOf(E element){
        if(element==null){
            双向链表.Node node=first;
            for (int i = 0; i ) node).next;
            }
        } else {
            双向链表.Node node=first;
            for (int i = 0; i  
 注意：
 
环形链表用快慢指针  快慢指针初始指向位置是不同的
 
动态数组缩容 *** 作：
 
 缩容和扩容差不多思想：把原来的元素移到新搞出来的数组内存
 
 
 二：双向链表
 
 
 找到对应index下标的节点node
 
因为这个节点node具有双指向性
 
next和prev指向 因此利用对称来找出对应索引处的节点
 
这样分一半一半的找
 
提高了效率
 
 
 
 
 clear:
 
当我们把linkedList对象的两条线去掉以后
 
整个节点数组都会死掉
 
虽然说仍然有引用互相进行指向
 
但这些节点已经丧失了gc root对象的指向
 
 
JVM宣布他们这些节点全部死掉
 
 
那么作用之后只剩下：
 
 
 
 双向链表add：
 
 
 
first只关注第一个节点元素
 
last只关注最后一个节点元素 
 
 
 
 但如果最开始什么都没有：
 
last==null
 
 
 只有一个
 
 
  
    public void addindex(int index,E elememt) {
        if (index < 0 || index > size) {
            return;
        }
        if (index == size) {
            Node oldlast=last;
            Node leo=new Node(element,oldlast,null);
            last=leo;
            if(oldlast==null){//当只有一个元素的时候first last都指向这个节点
                last=leo;
             first=leo;
            } else {
                oldlast.next=last;
            }
        } else {
            Node next = node(index);//找到要添加位置的节点
            Node prev = next.prev;//要添加的节点的上一个
            Node node = new Node(element, prev, next);
            next.prev = node;
            if (next.prev == null) {//index==0
                first = node;
            } else {
                prev.next = node;
            }
        }
 
 删除：
 
 
 
 
  
    public void remove(int index){
        Node node=node(index);
        Node prev=node.prev;//这里的prev next就相当于一个节点了吧
        Node next=node.next;
        if(prev==null){
            first=next;
        } else {
            prev.next=next;
        }
        if(next==null){
            last=prev;
        } else {
            next.prev=prev;
        }
    }
 
 
双向链表总代码：
 
package 链表动态数组.链表.双向链表;

import 链表动态数组.链表.单链表.leo;

public class 双向链表 extends leo {
    //元素的数量
    protected int size;
    protected static final int ELEMENT_NOT_FOUND=-1;
    protected Node first;
    private   Node last;
    
 public static class Node{
     public E element;
     Node prev;
     public Node next;
     public Node(E element, Node prev, Node next) {
         this.element = element;
         this.prev = prev;
         this.next = next;
     }
 }
    
    public void clear(){
        size=0;
        first=null;
        last=null;
    }
    
    public int size() {
        return size;
    }
    
    public boolean isEmpty(){
        return size==0;
    }
    
    public boolean contains(E elements){
        Node node=first;
        for (int i = 0; i < size; i++) {
            if(node.element==elements){
                return true;
            }
            node=node.next;
        }
        return false;
    }
    
    private Node node(int index){
        if(index<0||index>size){
            return null;
        }
        //当在左半边的时候
        if(index<(size>>1)){
            Node node=first;
            for (int i = 0; i  node=last;
            for (int i =size-1; i  node=node(index);
      E old=node.element;
      node.element=element;
      return old;//返回原来的元素值
    }
    
    public void addindex(int index,E elememt) {
        if (index < 0 || index > size) {
            return;
        }
        if (index == size) {
            Node oldlast=last;
            Node leo=new Node(element,oldlast,null);
            last=leo;
            if(oldlast==null){//当只有一个元素的时候first last都指向这个节点
                last=leo;
             first=leo;
            } else {
                oldlast.next=last;
            }
        } else {
            Node next = node(index);//找到要添加位置的节点
            Node prev = next.prev;//要添加的节点的上一个
            Node node = new Node(element, prev, next);
            next.prev = node;
            if (next.prev == null) {//index==0
                first = node;
            } else {
                prev.next = node;
            }
        }
    }
    
    public void remove(int index){
        Node node=node(index);
        Node prev=node.prev;
        Node next=node.next;
        if(prev==null){
            first=node;
        } else {
           prev.next=next;
        }
        if(next==null){
            last=node;
        } else {
            next.prev=prev;
        }
    }
    
    public int indexOf(E element){
        if(element==null){
            Node node=first;
            for (int i = 0; i  node=first;
            for (int i = 0; i  
 单向循环链表：这是单链表
 
 
 
 当什么都没有 第一次添加节点的时候
 
 
 
 
 
 删除：
 
 特殊情况：只有一个节点·
 
 
 
package 链表动态数组.链表.单链表;
//循环链表与单链表的不同之处就在于add和remove
public class 单向循环链表 extends 单链表 {
    @Override
    public void addindex(int index, Object elememt) {
        if(index<0||index>size){
            return;
        }
        if(index==0){
            Node node=new Node(elememt,first);
            first=node;
            //找到最后一个节点
            Node last=node(index-1);
            last.next=first;//循环链表的规定
        } else {
           Node prev=node(index-1);
           Node node=new Node(elememt,prev.next);
           prev.next=node;
        }
    }
    @Override
    public E remove2(int index) {
        if(index<0||index>size){
            return null;
        }
        if(index==0){
            if(size==1){
              first=null;
            } else {
                Node last=node(index-1);
                Node node=new Node<>(last.element,first.next);
                last=node;
            }
        } else {
            Node prev=node(index-1);
            Node node=prev.next;
            prev.next=node.next;
        }
        size--;
        return null;
    }
}
 
 双向循环链表：
 
 
 
 
 
 
 
 双向循环链表remove：
 
 
但是当链表原来只有一个节点的时候
 
上面代码应当修改： 
 
 
 
 
代码：
 
package 链表动态数组.链表.双向链表;
//循环链表与单链表的不同之处就在于add和remove
public class 双向循环链表 extends 双向链表 {
    @Override
    public void addindex(int index, Object elememt) {
        if(index==size){
            Node oldlast=last;
            Node node=new Node((E)elememt,oldlast,first);
            if(oldlast==null){
                first=last;
                first.prev=first;
                first.next=first;
            } else {
                oldlast.next=node;
                first.prev=node;
            }
        } else {
            Node next=node(index);
            Node prev=next.prev;
            Node node=new Node((E) elememt,prev,next);
            next.prev=node;
            if(prev==null){//证明index==0
               first=node;
            } else {
                prev.next=node;
            }
        }
        size++;
    }

    @Override
    public void remove(int index) {
        if (index < 0 || index > size) {
            return;
        }
        Node node = first;
        if (size == 1) {
            first = null;
            last = null;
        } else {
            node = node(index);
            Node prev = node.prev;
            Node next = node.next;
            prev.next = next;
            next.prev = prev;
            if(node==first){//index==0
                first=next;
            }
            if(node==last){//index==size-1
                last=prev;
            }
        }
    }
}
 
 
 
 
 1.
 
2.
 
 
 
 
 
 3.封装一个remove方法直接删除传进来的节点
 
 
 
 4.运行测试：
 
 
 
 
 
 
 
 
 
 
 
欢迎分享，转载请注明来源：内存溢出
原文地址:https://www.54852.com/zaji/5636814.html