栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

链表(一)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

链表(一)

链表

链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

上图中 第一行为单链表,(数据区和next指针区)
· 第二行为双链表(数据区,next指针区和last指针区)

单链表反转

用pre,next,head三个指针来完成对链表节点的不断记录,让链表节点的指针变换。

//定义单链表节点
    public static class Node{
        public int value;
        public Node next;
        public Node(int data){
            value=data;
        }
    }
//单链表反转
    public static Node reverseLinkedList(Node head){
        Node pre=null;
        Node next=null;
        while (head!=null){
            next=head.next;
            head.next=pre;
            pre=head;
            head=next;
        }
        return pre;
    }
双链表反转

双链表节点比单链表节点多了一个指向上一个节点的指针,使双链表比单链表更加灵活,但反转的思路跟单链表一样。

初始链表

进行反转的链表

    //定义双链表
    public static class DoubleNode{
        public int value;
        public DoubleNode last;
        public DoubleNode next;
        public DoubleNode(int data){
            value=data;
        }
    }
   //双链表反转
    public static DoubleNode reverseDoubleList(DoubleNode head){
        DoubleNode pre=null;
        DoubleNode next=null;
        while (head!=null){
            next=head.next;
            head.next=pre;
            head.last=next;
            pre=head;
            head=next;
        }
        return pre;
    }
单链表实现队列

数据结构中队列的特点为:先进先出
用链表实现,就需要有两个头尾指针变量来记录跟踪。



public class LinkedListToQueue {
    //单链表实现队列结构
    public static class Node{
        public V value;
        public Node next;

        public Node(V v){
            value=v;
            next=null;
        }
    }
    public static class MyQueue{
        private Node head;
        private Node tail;
        private int size;

        public MyQueue(){
            head=null;
            tail=null;
            size=0;
        }
        //判断队列是否为空
        public boolean isEmpty(){
            return size==0;
        }
        //得到队列的尺寸
        public int size(){
            return size;
        }
        //进入队列
        public void offer( V value){
            Node cur=new Node<>(value);
            if (tail==null){
                head=cur;
                tail=cur;
            }else {
                tail.next=cur;
                tail=cur;
            }
            size++;
        }
        //弹出队列
        public V poll(){
            V ans=null;
            if (head!=null){
                ans=head.value;
                head=head.next;
                size--;
            }
            if (head == null){
                tail=null;
            }
            return ans;
        }
        //只得到值不弹出
        public V peek() {
            V ans=null;
            if (head!=null){
                ans=head.value;
            }
            return ans;
        }
    }
}
单链表实现栈结构

栈结构的特点为:先进后出
相对于队列结构,写栈结构的思路更加简单一些,只需要不断让进栈的节点往下沉。


public class LinkedListToStack {
    public static class Node{
        public V value;
        public Node next;

        public Node(V v) {
            value = v;
            next = null;
        }
        public static class MyStack{
            private Node head;
            private int size;
            public MyStack(){
                head=null;
                size=0;
            }
            //判断是否为空
            public boolean isEmpty(){
                return size==0;
            }
            //得到栈的长度
            public int size(){
                return size;
            }
            //推入栈顶
            public void push(V value){
                Node cur=new Node<>(value);
                if (head!=null){
                    cur.next=head;
                    head=cur;
                }else{
                    head=cur;
                }
                size++;
            }
            //出栈
            public V pop(){
                V ans=null;
                if (head!=null){
                    ans=head.value;
                    head=head.next;
                    size--;
                }
                return ans;
            }
            //得到节点的数据
            public V peek(){
                return head!=null?head.value:null;
            }
        }
    }
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/980879.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号