链表的概念以及基本操作：头插、尾插、头删、尾删

你的名字 2023-07-16 14:58 31阅读 0赞

## 链表 ##

1.**链表的概念**：链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。（逻辑上有前后关系，物理上不保证前后关系）  
2\*\*.链表的基本操作：\*\*头插、尾插、头删、尾删

class Node {
        
        int val ;
        Node next ;
    
        public Node(int val){
        
         this.val = val;
         this.next = null;
        }
    
        @Override
          public String toString() {
        
              return String.format("Node(%d)",val);
          }
    }
    public class MyLinkedList {
        
        //头插
        private static Node pushFront(Node head, int val){
        
            Node node = new Node(val);
            node.next = head;
            return node;
        }
        //尾插
        private static Node pushBack(Node head, int val){
        
            Node node = new Node(val);
            if(head == null){
        
                return node;
            }else{
        
                Node last = head;
                while(last.next != null){
        
                    last = last.next;
                }
                last.next = node;
            }
            return head;
        }
    
        //头删
        private static Node popFront(Node head){
        
            if(head == null){
        
                System.out.println("空链表无法删除！");
                return null;
            }
            return head.next;
        }
        //尾删(***)
        private static Node popBack(Node head){
        
            if(head == null){
        
                System.out.println("空链表无法删除！");
                return null;
            }
            if(head.next == null){
        
                return null;
            }else{
        
                Node lastSecond = head;
                while(lastSecond.next.next != null){
        
                    lastSecond = lastSecond.next;
                }
                lastSecond.next = null;
                return head;
            }
        }

**测试代码：**

public static void main(String[] args) {
        
            Node head = null;
    
            head = pushFront(head, 0);
            head = pushFront(head, 1);
            head = pushFront(head, 2);
            // 打印
            print(head);	// 2 1 0
    
            // 尾插
            head = popFront(head);
            print(head);	// 1 0
    
            head = pushBack(head, 10);
            head = pushBack(head, 20);
            head = pushBack(head, 30);
            print(head);	// 1 0 10 20 30
    
            head = popBack(head);
            head = popBack(head);
            print(head);//1 0 10
    
            head = pushBack(head, 100);
            print(head);// 1 0 10 100
        }
        // 打印
        private static void print(Node head) {
        
            System.out.println("打印链表：");
            for (Node cur = head; cur != null; cur = cur.next) {
        
                System.out.print(cur + " --> ");
            }
            System.out.println("null");
        }
    }