数据结构之链表及Java实现

末蓝、 2022-05-27 05:26 178阅读 0赞

## 一、链表的基本介绍 ##

链表是最基本的数据结构，Java中LinkedList的实现原理就是链表。链表是由多个节点组成的，每个节点只存储数据和下一个节点的位置，这样就可以一级一级地将多个节点串在一起，最后一个节点指向为空，因此链表不需要连续的内存空间，存储是分散的，通过每个节点的地址将各个节点连起来。链表向外暴露的只有一个头节点，通过头节点就可以对整个链表进行操作，链表在进行循环遍历时效率不高，但是插入和删除时优势明显。

## 二、链表的Java实现 ##

public class Link {
    
        class Node{
            Node next = null;//指向下一个节点
            int data;//节点的值
            public Node(int data){
                this.data = data;
            }
        }
    
        Node head = null;//定义链表头节点
    
    
        //向链表中添加数据
        public void addNode(int data){
            Node newNode = new Node(data);
            if(head == null){
                head = newNode;
                return;
            }
            newNode.next = head;
            head = newNode;
        }
        //向链表中添加节点
        public void addNode(Node n){
            if(head == null){
                head = n;
            }
            n.next = head;
            head = n;
        }
        //返回链表的长度
        public int length(){
            int num = 1;
            if(head == null){
                return 0;
            }
            Node tmp = head;
            while(tmp.next!=null){
                num++;
                tmp = tmp.next;
            }
            return num;
        }
        //删除第index个节点
        public boolean delNode(int index){
            if(index<1||index>length()){
                return false;
            }
            if(index == 1){
                head = head.next;
                return true;
            }
            int i = 1;
            Node preNode = head;
            Node curNode = head.next;
            while(curNode!=null){
                i++;
                if(index == i){
                    preNode.next = curNode.next;
                    return true;
                }
                preNode = curNode;
                curNode = curNode.next;
            }
            return false;
        }
        //打印链表中的数据
        public void printLink(){
            Node tmp = head;
            while(tmp.next!=null){
                System.out.print(tmp.data + " ");
                tmp = tmp.next;
            }
            System.out.print(tmp.data);
            System.out.println();
        }
        //删除某个节点
        public boolean delNode(Node n){
            if(n == null){
                return false;
            }
            if(n == head){
                head = head.next;
                return true;
            }
            Node preNode = head;
            Node curNode = head.next; 
            while(curNode != null){
                if(curNode == n){
                    preNode.next = curNode.next;
                    return true;
                }
                preNode = curNode;
                curNode = curNode.next;
            }
            return false;
    
        }
        //不知道头节点的情况下，删除某节点
        public boolean deleteNode(Node n){
            if(n == null){
                return false;
            }
            if(n.next ==  null){
                n = null;
                return true;
            }
            n.data = n.next.data;
            n.next = n.next.next;
            return true;
        }
        public static void main(String args[]){
            Link link = new Link();
            link.addNode(1);
            link.addNode(2);
            link.addNode(3);
            link.addNode(4);
            link.printLink();
            link.addNode(5);
            link.printLink();
            System.out.println("length: " + link.length());
            System.out.println("del index 3: " + link.delNode(3));
            link.printLink();
            System.out.println("del index 4: " + link.delNode(4));
            link.printLink();
        }
    }

输出内容：

4 3 2 1
    5 4 3 2 1
    length: 5
    del index 3: true
    5 4 2 1
    del index 4: true
    5 4 2

## 三、链表相关算法实现 ##

1.反转链表  
反转链表可以通过两种方法来实现，遍历反转和递归反转。

a.遍历反转法是从前往后反转各个结点的指针域的指向。

public void reserveLink(){
            if(head == null || head.next == null){
                return;
            }
            Node preNode = head;
            Node curNode = head.next;
            Node pretmp;
            Node curtmp;
            Node newHead;
            while(curNode != null){
                curtmp = curNode.next;
                pretmp = curNode;   
                curNode.next = preNode;
                if(curtmp == null){
                    newHead = curNode;
                }
                preNode = pretmp;
                curNode = curtmp;
            }
            head.next = null;
            newHead = preNode;
            this.head = newHead;
            return;
        }

b.递归反转法是从后往前逆序反转指针域的指向，需要获取头节点。  
实现代码如下：

public Node reserveLink2(Node head) {  
            // head看作是前一节点，head.next()是当前节点，reHead是反转后新链表的头节点  
            if (head == null || head.next == null) {  
                return head;// 若为空链或者当前结点在尾节点，则直接还回  
            }  
            Node reHead = reserveLink2(head.next);//反转后续节点 
            head.next.next = head;// 将当前结点的指针域指向前一节点  
            head.next = null;// 前一节点的指针域令为null;  
            return reHead;//反转后新链表的头节点  
        }

2.删除链表中的重复节点  
主要思路是两次循环，分别比较data，相等时，当前节点的下一个节点指向data位置节点的下一个节点。

public void delRep(){
            Node tmp = head;    
            while(tmp!=null){
                int t = tmp.data;
                Node tmp2 = tmp;
                while(tmp2.next!=null){
                    int j = tmp2.next.data;
                    if(t == j){
                        tmp2.next = tmp2.next.next;
                    }
                    else{
                        tmp2 = tmp2.next;
                    }
                }
                tmp = tmp.next;
            }
        }