数据结构与算法Java版——单链表的实现

痛定思痛。 2022-06-12 23:27 174阅读 0赞

> 　　上次分享的是线性表的实现，不知道各位小伙伴有没有自己动手实现，不过进度不能停。今天记录单链表的实现。虽然Java并没有c++中的指针（真的没有吗？我觉得应该算有的，至少是有伪指针），但是依然可以实现链表，我们可以在Java中用引用变量指向我们的节点，让引用变量代替指针的作用。  
> 　　这个学期学了数据结构这本书，所以我打算用Java实现其中表，队，栈，树。如果你有兴趣可以持续关注我后续操作。我的个人博客地址为[我的博客][Link 1]
> 
> ![这里写图片描述][53096650.jpg]

接下来我们就一步步实现吧。

首先我们要知道什么是节点，在Java中并没有struct，但是我们可以创建一个Node类来表示节点。

public class Node<T> {
        private T data; //节点的数据
        public Node next; //指向的下一个节点
        public Node(T data, Node next) {
            this.data = data;
            this.next=next;
        }
        public Node() { }
        public T getData() {
            return data;
        }
        private void setData(T data) {
            this.data = data;
        }
    }

然后我们需要创建一个链表LinkList类，给它一些基本的属性方法，以及创建构造函数等等。

public class LinkList<T> {
        private Node head;  //头结点
        private Node tail;  //尾结点
        private int size;   //链表长度
    
        public LinkList() {
            head=null;
            tail=null;
        }
    
        //获取链表长度
        public int getLength(){
            return size;
        }
    
        //是否含有元素
        public boolean isEmpty(){
            return size==0;
        }
    
        //清空链表
        public void clear(){
            head=null;
            tail=null;
            size=0;
        }
    }

完成以上操作就可以创建一个单链表了。接下来实现LinkList类中的重要方法。

**通过索引获取节点的方法，这应该算是一个中间方法，为实现插入删除做铺垫。**

//通过索引获取节点
        public Node getNodeByIndex(int index){
            if(index<0||index>size-1){
                throw new IndexOutOfBoundsException("索引越界");
            }
            Node node=head;
            for(int i=0;i<size;i++,node=node.next){
                if(i==index){
                    return node;
                }
            }
            return null;
        }

**插入方法：个人建议分开写（我是一起写的，发现逻辑会太乱，反正我最后还是分开写了）**  
**- 头插入**  
**- 尾插入**  
**- 中间插入（在这个方法中包含头插入与尾插入）**

//头插入
        public void  addAtHead(T element){
            head=new Node<T>(element, head);
            //如果是空链表就变让尾指针指向头指针
            if(tail==null){
                tail=head;
            }
            size++;
        }
    
        //尾插入
        public void addAtTail(T element){
            //如果表为空
            if(head==null){
                head=new Node<T>(element, null);
                tail=head;
            }else{
                Node node=new Node<T>(element, null);
                tail.next=node;
                tail=node;  //尾节点后移
            }
            size++;
        }
    
        //在指定位置插入元素
        public void insert(T element,int index){
            if(index<0||index>size){
                throw new IndexOutOfBoundsException("索引越界");
            }
            if(index==0){
                addAtHead(element);
            }else if(index>0&&index<size-1){
                //中间插入
                Node nexNode=null;
                Node insNode=new Node<T>(element, nexNode);
                nexNode=getNodeByIndex(index);
                Node preNode=getNodeByIndex(index-1);
                preNode.next=insNode;
                insNode.next=nexNode;
                size++;
            }else {
                addAtTail(element);
            }
        }

**删除方法：**

**- 删除指定位置元素**  
**- 删除最后一个位置的元素**

//删除指定位置的元素
        public void delete(int index){
            if(index<0||index>size-1){
                throw new IndexOutOfBoundsException("索引越界");
            }
            int flag=index-1;
            Node node=getNodeByIndex(index);
            if(flag < 0){
                //flag<0说明删除的是第一个元素，将头结点指向下一个就行
                head=head.next;
                node=null;
            }else{
                Node preNode=getNodeByIndex(index-1);
                preNode.next=node.next;
                //如果删除的是最后一个元素，尾节点前移一位
                if(index==size-1){
                    tail=preNode;
                }
            }
            size--;
        }
    
        //删除最后一个元素
        public void remove(){
            delete(size-1);
        }

**最后实现其他方法（locate找位置，get通过索引获得值，toString直接输出数组），这个单链表的实现就完成了。**

@Override
        public String toString() {
            StringBuilder sb=new StringBuilder();
            Node node=head;
            for(int i=0;i<size;i++,node=node.next)
            {
                sb=sb.append(node.getData()+" ");
            }
            return sb+"";
        }
    
        //获得指定位置元素
        public T get(int index){
            return (T) getNodeByIndex(index).getData();
        }
    
        //获得指定元素的索引
        public T locate(T element){
            Node node=head;
            StringBuilder sb=new StringBuilder();
            for(int i=0;i<size;i++,node=node.next)
            {
                if(element.equals(node.getData()))
                {
                    sb=sb.append(i+" ");
                }
            }
            if(sb.length()<=0)
                return (T)"无此元素";
            return (T) sb;
        }

以上就完成了所有操作，如果小伙伴你懒得实现了，直接复制粘贴也可以成功，最后附上运行结果图：  
![这里写图片描述][28977179.jpg]

这是单链表的实现，**如果要做循环链表只需要将tail尾节点指向head头结点即可**，有兴趣的小伙伴自己去实现吧。

[Link 1]: http://xichangblog.com/2017/06/21/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84Java%E7%89%88%E2%80%94%E2%80%94%E5%8D%95%E9%93%BE%E8%A1%A8%E7%9A%84%E5%AE%9E%E7%8E%B0/#more
[53096650.jpg]: http://or0um8wrx.bkt.clouddn.com/17-6-21/53096650.jpg
[28977179.jpg]: http://or0um8wrx.bkt.clouddn.com/17-6-21/28977179.jpg