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

简单双向链表

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

简单双向链表

package algorithm3;

import java.util.Iterator;


public class TwoWayLinkList implements Iterable{

    //定义双向链表的成员变量
    private Node head;   //记录首结点
    private Node last;   //记录尾结点
    private int N;       //记录链表内元素个数



    //首先定义一个内部类,结点类
    private class Node {
        //内部类(Node)的成员变量
        private Node pre;
        private Node next;
        private T item;
        //内部类(Node)的构造方法
        public Node(T item,Node pre,Node next) {
            this.pre = pre;
            this.next = next;
            this.item = item;
        }
    }

    //构造方法,即初始化双向链表
    public TwoWayLinkList() {
        this.head = new Node(null,null,null);
        this.last = null;
        this.N = 0;
    }


    //双向链表的成员方法
    //1.清空链表
    public void clear() {
        //1.让头结点不往后指,让last结点为空,让元素个数为0
        head.next =null;
        last = null;
        N = 0;
    }

    //2.获取链表长度
    public int length() {
        return N;
    }

    //3.判断链表是否为空
    public boolean isEmpty() {
        return N==0;
    }

    //4.获取第一个元素
    public T getFirst() {
        //判断链表是否为空
        if (!isEmpty()) {
            Node n = head;
            return n.next.item;
        }
        return null;
    }

    //5.获取最后一个元素
    public T getLast() {
        if (!isEmpty()) {
            return last.item;
        }
        return null;
    }

    //6.插入元素t 即在最后插入一个元素,创建一个过度元素,把最后一个节点的copy到这个过度元素,
    //要新插入的元素放到last节点内
    public void insert(T t) {
        //分为当前链表为空与不为空的两种情况
        if (isEmpty()) {
            //为空
            last = new Node(t,head,null);        //让这个新结点成为尾结点,并且它的前指针指向头结点
            head.next = last;                        //让头结点的后指针指向这个新结点
        }
        else{
            //不为空
            //之前的尾结点变为老的尾结点
            Node oldLast = last;
            //创建新结点,让它的前指针直向老的尾结点
            Node newNode = new Node(t,oldLast,null);
            //让老的尾结点直向新节点
            oldLast.next = newNode;
            //让新节点成为尾结点
            last = newNode;
        }
        //元素个数加1
        N++;
    }

    //6.在指定位置i处插入元素t
    public void insert(int i,T t) {
        //找到i-1位置的结点
        Node n =head;
        for (int index=0; index<=i-1; index++) {
            n=n.next;
        }
        找到i位置的结点
        Node curr = n.next;
        //创建新结点,让i-1位置处的结点的后指针指向这个结点
        Node newNode = new Node(t,n,curr);
        n.next=newNode;
        curr.pre=newNode;
        //元素的个数加一
        N++;
    }

    //7.获取指定位置i处的元素
    public T get(int i) {
        //找到i位置的结点
        Node n =head;
        for (int index=0; index<=i; index++) {
            n=n.next;
        }
        return n.item;
    }

    //8.查找元素t在链表中第一次出现的位置
    public int indexOf(T t) {
        Node n =head;
        for (int index=0; index iterator() {
        return new IteratorImpl();
    }

    public class IteratorImpl implements Iterator {
        //内部类IteratorImpl的成员变量
        private Node n;
        //构造方法
        public IteratorImpl() {
            this.n = head;
        }

        @Override
        public boolean hasNext() {
            return n.next!=null;
        }

        @Override
        public Object next() {
            n=n.next;
            return n.item;
        }
    }

}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/950738.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

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

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