算法通关村|青铜挑战----链表

前言：数据结构的基础：创建+增删改查

学习目标：单链表的创建+增删改查，双链表的创建+增删改查

1单链表的基础与构造方法

1.1单链表的的内部结构

数据域+指针域

数据域:当前节点的元素值

指针域：当前节点保存的下一个节点的元素的地址，其中最后一个元素的指针域指向null

标准的面向对象的节点的定义：

public class ListNode {
private int data;
private ListNode next;

public ListNode(int data) {
this.data = data;
}

public int getVal() {
return data;
}

public void setVal(int val) {
this.data = val;
}

public ListNdoe getNext() {
return next;
}

public void setNext(ListNdoe next) {
this.next = next;
}
}

LeetCode中节点的定义

public class ListNode{
    public int val;
    public ListNode next;
    ListNode(int val){
        val=x;
        next=null;
    } 
}
ListNode listnode=new ListNode(1);

上述代码创建对象后可直接使用listnode.val和listnode.next

1.2遍历链表

单链表遍历：从头开始逐个访问,一定要找到表头

public static int getListLength(Node head){
    int length=0;
    Node node=head;
    while(node!=null){
       length++;
       node=node.next; 
    }
    return length;
}

1.3链表的插入

头部插入：创建新节点newnode,newnode.next=head;head=newnode;头节点要重新指向新的节点

中间插入：找到要插入位置的前一个节点

尾部插入：找到最后一个节点，直接将新的节点插入到尾部

 链表插入
     * @param head       链表头节点
     * @param nodeInsert 待插入节点
     * @param position   待插入位置，从1开始
     * @return 插入后得到的链表头节点
     */
   
public static Node InsertNode（Node head,Node nodeInsert,int position）{
        if(head==null){
        //这里既可以认为待插入的节点就是链表的头节点，也可以抛出不能插入的异常,一般倾向于前者
        return nodeInsert;
    }
        int size=getListLength(head);
        if(position>size+1||position<1){
        System.out.println("插入的位置越界");
        return head;

    }
        //链表的头部插入
        if(position==1){
        nodeInsert.next=head;
        head=nodeInsert;
        return head;
    }
        //中部插入
        Node pNode=head;
        int count=1;
        //这里position被上面的size限制住了，不用考虑pNode=null
        while(count<position-1){
        pNode=pNode.next;
        count++;
    }
        nodeInsert.next=pNode.next;
        pNode.next=nodeInsert;
        return head;
       

}

1.4链表的删除

1.删除链表的头节点：执行head=head.next;

2.删除中间节点：cur.next=cur.next.next找到要删除节点的前驱节点

3.删除最后一个节点：找到要删除节点的前驱节点

链表删除
     * @param head       链表头节点
     * @param position   删除节点位置，从1开始
     * @return 删除后得到的链表头节点
     */
    public static ListNode deleteNode(ListNdoe head,int position){
        if(head==null){
        return head;
    }
        int size=getListLength(head);
        if(position<1||position>size){    
        System.out.println("输入的参数有误")；
    }
        if(postion==1){
        return head.next;   
    }else{
        ListNode preNode=head;
        int count=1;
        while(count<position-1){
        preNode=preNode.next;
        count++;
        }
        ListNode curNode=preNode.next;
        preNode=curNode.next;
    }
        return head;
}

上述完整代码及测试代码如下

package d1_链表;

public class NodeDemo {
    public static void main(String[] args) {
        // 创建一个链表：1 -> 2 -> 3 -> 4 -> null
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        printList(head);
        // 插入一个节点到链表头部：0 -> 1 -> 2 -> 3 -> 4 -> null
        ListNode nodeInsert1 = new ListNode(0);
        head = InsertNode(head, nodeInsert1, 1);
        printList(head);

        // 插入一个节点到链表中部：0 -> 1 -> 2 -> 5 -> 3 -> 4 -> null
        ListNode nodeInsert2 = new ListNode(5);
        head = InsertNode(head, nodeInsert2, 4);
        printList(head);

        // 插入一个节点到链表末尾：0 -> 1 -> 2 -> 5 -> 3 -> 4 -> 6 -> null
        ListNode nodeInsert3 = new ListNode(6);
        head = InsertNode(head, nodeInsert3, 7);
        printList(head);
        System.out.println("------------------");
        // 创建一个链表：1 -> 2 -> 3 -> 4 -> null
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(3);
        head1.next.next.next = new ListNode(4);
        printList(head1);

        // 删除链表的第一个节点：2 -> 3 -> 4 -> null
        head1 = deleteNode(head1, 1);
        printList(head1);

        // 删除链表的第三个节点：2 -> 3 -> null
        head1 = deleteNode(head1, 2);
        printList(head1);

        // 删除链表的最后一个节点：2 -> null
        head1 = deleteNode(head1, 2);
        printList(head1);

        }
    public static int getListLength(ListNode head) {
        int length = 0;
        ListNode node = head;
        while (node != null) {
            length++;
            node = node.next;
        }
        return length;
    }

    public static ListNode InsertNode(ListNode head, ListNode nodeInsert, int position) {
        if (head == null) {
            //这里既可以认为待插入的节点就是链表的头节点，也可以抛出不能插入的异常,一般倾向于前者
            return nodeInsert;
        }
        int size = getListLength(head);
        if (position > size + 1 || position < 1) {
            System.out.println("插入的位置越界");
            return head;

        }
        //链表的头部插入
        if (position == 1) {
            nodeInsert.next = head;
            head = nodeInsert;
            return head;
        }
        //中部插入
        ListNode pNode = head;
        int count = 1;
        //这里position被上面的size限制住了，不用考虑pNode=null
        while (count < position - 1) {
            pNode = pNode.next;
            count++;
        }
        nodeInsert.next = pNode.next;
        pNode.next = nodeInsert;
        return head;


    }
    /**
     * 从链表中删除指定位置的节点
     * @param head       链表头节点
     * @param position   删除节点位置，从1开始
     * @return 删除后得到的链表头节点
     */
    public static ListNode deleteNode(ListNode head, int position) {
        if (head == null) {
            return null;
        }
        int size = getListLength(head);
        if (position < 1 || position > size) {
            System.out.println("输入的参数有误");
            return head;
        }
        if (position == 1) {
            return head.next;
        } else {
            ListNode preNode = head;
            int count = 1;
            while (count < position - 1) {
                preNode = preNode.next;
                count++;
            }
            preNode.next = preNode.next.next;
        }
        return head;
    }

    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " -> ");
            head = head.next;
        }
        System.out.println("null");
    }


    }
class ListNode {
    public int val;
    public ListNode next;

    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

结果：
1 -> 2 -> 3 -> 4 -> null
0 -> 1 -> 2 -> 3 -> 4 -> null
0 -> 1 -> 2 -> 5 -> 3 -> 4 -> null
0 -> 1 -> 2 -> 5 -> 3 -> 4 -> 6 -> null
------------------
1 -> 2 -> 3 -> 4 -> null
2 -> 3 -> 4 -> null
2 -> 4 -> null
2 -> null

2.双向链表

补充：针对插入删除的链表为，只有一个节点的first=null,或last=null

这些代码中 first=null 和 last=null 的含义是不同的。

first 和 last 都是 DoubleNode 类型的变量，分别代表双向链表的头节点和尾节点。

在构造函数中，first=null 的含义是将头节点初始化为 null，表示链表为空。而 last=null 的含义是将尾节点初始化为 null，表示链表中没有任何一个节点。

在双向链表中，如果链表为空，那么头节点和尾节点都应该为 null。如果链表中只有一个节点，则头节点和尾节点指向同一个节点。

当向链表中插入新节点时，需要根据链表的当前状态分别更新 first 和 last 的值。

例如，当链表为空时，插入第一个节点时，需要将 first 和 last 都指向这个节点；当链表中已经有节点时，插入新节点时只需要更新 last 的值即可。

同样的道理，在从双向链表中删除节点时，也需要根据链表的当前状态来分别更新 first 和 last 的值。

因此，对于双向链表来说，first=null 和 last=null 的含义是不同的，它们分别代表链表的头节点和尾节点是否为空。文章来源地址https://www.toymoban.com/news/detail-610790.html

package d1_链表;

public class DoubleLinkList {
    private int data;//数据域
      private DoubleNode first;
      private  DoubleNode last;
      public  DoubleLinkList(){
          first=null;
          last=first;
      }
      //从头部开始打印
        public void diaplayForward(){
            System.out.println("List(first---->last):");
            DoubleNode current=first;
            while(current!=null){
                current.displayNdoe();
                current=current.next;
            }
            System.out.println();
        }
        //从尾部开始打印
    public void displayBackward(){
        System.out.println("List(last---->first)");
        DoubleNode current=last;
        while(current!=null){
            current.displayNdoe();
            current=current.prev;
        }
        System.out.println();
    }
    public boolean isEmpty(){
          return (first==null);
    }
    //头部插入元素
    public void insertFirst(int data){
          DoubleNode newDoubleNode=new DoubleNode(data);
          if(isEmpty()){
              last=newDoubleNode;
          }else{//如果不是第一个节点
              first.prev=newDoubleNode;
          }
          newDoubleNode.next=first;
          //将新节点复制给first(链接)成为第一个节点
        first=newDoubleNode;
    }
    //尾部插入元素
    public void insertLast(int data){
        DoubleNode newDoubleNode=new DoubleNode(data);
          if(isEmpty()){
              first=newDoubleNode;
          }else {
              newDoubleNode.prev=last;
              last.next=newDoubleNode;
          }
          //由于插入一个新的节点，又因为是尾部插入，所以将last指向newNode
          last=newDoubleNode;
    }
    public void insertAfter(int key,int data){
          DoubleNode newDoublenode=new DoubleNode(data);
          DoubleNode current=first;
          while((current!=null)&&(current.data!=key)){
              current=current.next;
          }
          //若当前节点current为空
        if(current==null){
            if(isEmpty()){
                first=newDoublenode;
                last=newDoublenode;
            }else {
                 //2.找不到key的值，则在链表尾部插入一个新的节点
                last.next=newDoublenode;
                newDoublenode.prev=last;
                last=newDoublenode;
            }
        }else{//第三种情况，找到key的值，分两种情况
            if(current==last){
                //1.key值与最后节点的data相等
                newDoublenode.next=null;
                last=newDoublenode;
            }else{
                //2.两节点中间插入
                newDoublenode.next=current.next;
                current.next.prev=newDoublenode;
            }
            current.next=newDoublenode;
            newDoublenode.prev=current;

        }

    }
    //删除首元素
    public DoubleNode deleteFirst(){
          DoubleNode temp=first;
          //若链表只有一个节点，删除后链表为空，将last指向null
        if(first.next==null){
            last=null;
        }else{
            //若链表有两个及以上的节点，因为是头部删除，则first.next将变成第一个
            first.next.prev=null;
        }
            first=first.next;
          return temp;
    }
    //删除尾部元素
    public DoubleNode deleteLast(){
          DoubleNode temp=last;
          if(first.next==null){
              first=null;
          }else{
              last.prev.next=null;
          }
          last=last.prev;
          return temp;
    }
    //删除中间元素
    public DoubleNode deleteKey(int key){
        DoubleNode current=first;
        while((current!=null)&&(current.data!=key)){
            current=current.next;
        }
        if(current==null){
            return null;
        }else{
            if(current==first){
                first=current.next;
                current.next.prev=null;
            }else if(current==last){
                last=current.prev;
                current.prev.next=null;

            }else{
                current.prev.next=current.next;
                current.next.prev=current.prev;
            }
        }
        return current;
    }



}
class DoubleNode {
    public int data;
    public DoubleNode prev;
    public DoubleNode next;

    public DoubleNode(int data) {
        this.data = data;
    }
    public void displayNdoe(){
        System.out.println("{"+data+"}");
    }
}
//测试类
package d1_链表;

public class DoubleLinkListTest {
    public static void main(String[] args) {
        DoubleLinkList list = new DoubleLinkList();

        // 在链表头部插入元素
        list.insertFirst(10);
        list.insertFirst(20);
        list.insertFirst(30);
        System.out.println("从头部开始打印链表：");
        list.diaplayForward();

        // 在链表尾部插入元素
        list.insertLast(40);
        list.insertLast(50);
        list.insertLast(60);
        System.out.println("从尾部开始打印链表：");
        list.displayBackward();

        // 删除头部元素
        DoubleNode first = list.deleteFirst();
        System.out.println("从头部删除元素：" + first.data);
        list.diaplayForward();

        // 删除尾部元素
        DoubleNode last = list.deleteLast();
        System.out.println("从尾部删除元素：" + last.data);
        list.displayBackward();

        // 在中间插入元素
        list.insertAfter(20, 70);
        list.insertAfter(40, 80);
        System.out.println("在中间插入元素后：");
        list.diaplayForward();

        // 删除中间元素
        DoubleNode node = list.deleteKey(30);
        System.out.println("删除中间元素：" + node.data);
        list.displayBackward();
    }
}
从头部开始打印链表：
List(first---->last):
{30}
{20}
{10}

从尾部开始打印链表：
List(last---->first)
{60}
{50}
{40}
{10}
{20}
{30}

从头部删除元素：30
List(first---->last):
{20}
{10}
{40}
{50}
{60}

从尾部删除元素：60
List(last---->first)
{50}
{40}
{10}
{20}

在中间插入元素后：
List(first---->last):
{20}
{70}
{10}
{40}
{80}
{50}

到了这里，关于算法通关村|青铜挑战----链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！