java 线性表---------双向链表（源代码）

心已赠人 2023-10-13 16:08 67阅读 0赞

1.public class DuLinkList<T>   
    2.{   
    3.    //定义一个内部类Node，Node实例代表链表的节点。   
    4.    private class Node   
    5.    {   
    6.        //保存节点的数据   
    7.        private T data;   
    8.        //指向上个节点的引用   
    9.        private Node prev;   
    10.        //指向下个节点的引用   
    11.        private Node next;   
    12.        //无参数的构造器   
    13.        public Node()   
    14.        {   
    15.        }   
    16.        //初始化全部属性的构造器   
    17.        public Node(T data , Node prev , Node next)   
    18.        {   
    19.            this.data = data;   
    20.            this.prev = prev;   
    21.            this.next = next;   
    22.        }   
    23.    }   
    24.    //保存该链表的头节点   
    25.    private Node header;   
    26.    //保存该链表的尾节点   
    27.    private Node tail;   
    28.    //保存该链表中已包含的节点数   
    29.    private int size;   
    30.    //创建空链表   
    31.    public DuLinkList()   
    32.    {   
    33.        //空链表，header和tail都是null   
    34.        header = null;   
    35.        tail = null;   
    36.    }   
    37.    //以指定数据元素来创建链表，该链表只有一个元素   
    38.    public DuLinkList(T element)   
    39.    {   
    40.        header = new Node(element , null , null);   
    41.        //只有一个节点，header、tail都指向该节点   
    42.        tail = header;   
    43.        size++;   
    44.    }   
    45.    //返回链表的长度      
    46.    public int length()   
    47.    {   
    48.        return size;   
    49.    }   
    50.  
    51.    //获取链式线性表中索引为index处的元素   
    52.    public T get(int index)   
    53.    {   
    54.        return getNodeByIndex(index).data;   
    55.    }   
    56.    //根据索引index获取指定位置的节点   
    57.    private Node getNodeByIndex(int index)   
    58.    {   
    59.        if (index < 0 || index > size - 1)   
    60.        {   
    61.            throw new IndexOutOfBoundsException("线性表索引越界");   
    62.        }   
    63.        if (index <= size / 2)   
    64.        {   
    65.            //从header节点开始   
    66.            Node current = header;   
    67.            for (int i = 0 ; i <= size / 2 && current != null  
    68.                ; i++ , current = current.next)   
    69.            {   
    70.                if (i == index)   
    71.                {   
    72.                    return current;   
    73.                }   
    74.            }   
    75.        }   
    76.        else  
    77.        {   
    78.            //从tail节点开始搜索   
    79.            Node current = tail;   
    80.            for (int i = size - 1 ; i > size / 2 && current != null  
    81.                ; i++ , current = current.prev)   
    82.            {   
    83.                if (i == index)   
    84.                {   
    85.                    return current;   
    86.                }   
    87.            }   
    88.        }   
    89.        return null;   
    90.    }   
    91.    //查找链式线性表中指定元素的索引   
    92.    public int locate(T element)   
    93.    {   
    94.        //从头节点开始搜索   
    95.        Node current = header;   
    96.        for (int i = 0 ; i < size && current != null  
    97.            ; i++ , current = current.next)   
    98.        {   
    99.            if (current.data.equals(element))   
    100.            {   
    101.                return i;   
    102.            }   
    103.        }   
    104.        return -1;   
    105.    }   
    106.    //向线性链式表的指定位置插入一个元素。   
    107.    public void insert(T element , int index)   
    108.    {   
    109.        if (index < 0 || index > size)   
    110.        {   
    111.            throw new IndexOutOfBoundsException("线性表索引越界");   
    112.        }   
    113.        //如果还是空链表   
    114.        if (header == null)   
    115.        {   
    116.            add(element);   
    117.        }   
    118.        else  
    119.        {   
    120.            //当index为0时，也就是在链表头处插入   
    121.            if (index == 0)   
    122.            {   
    123.                addAtHeader(element);   
    124.            }   
    125.            else  
    126.            {   
    127.                //获取插入点的前一个节点   
    128.                Node prev = getNodeByIndex(index - 1);   
    129.                //获取插入点的节点   
    130.                Node next = prev.next;   
    131.                //让新节点的next引用指向next节点，prev引用指向prev节点   
    132.                Node newNode = new Node(element , prev , next);   
    133.                //让prev的next指向新节点。   
    134.                prev.next = newNode;   
    135.                //让prev的下一个节点的prev指向新节点   
    136.                next.prev = newNode;   
    137.                size++;   
    138.            }   
    139.        }   
    140.    }   
    141.    //采用尾插法为链表添加新节点。   
    142.    public void add(T element)   
    143.    {   
    144.        //如果该链表还是空链表   
    145.        if (header == null)   
    146.        {   
    147.            header = new Node(element , null , null);   
    148.            //只有一个节点，header、tail都指向该节点   
    149.            tail = header;   
    150.        }   
    151.        else  
    152.        {   
    153.            //创建新节点,新节点的pre指向原tail节点   
    154.            Node newNode = new Node(element , tail , null);   
    155.            //让尾节点的next指向新增的节点   
    156.            tail.next = newNode;   
    157.            //以新节点作为新的尾节点   
    158.            tail = newNode;   
    159.        }   
    160.        size++;   
    161.    }   
    162.    //采用头插法为链表添加新节点。   
    163.    public void addAtHeader(T element)   
    164.    {   
    165.        //创建新节点，让新节点的next指向原来的header   
    166.        //并以新节点作为新的header   
    167.        header = new Node(element , null , header);   
    168.        //如果插入之前是空链表   
    169.        if (tail == null)   
    170.        {   
    171.            tail = header;   
    172.        }   
    173.        size++;   
    174.    }   
    175.    //删除链式线性表中指定索引处的元素   
    176.    public T delete(int index)   
    177.    {   
    178.        if (index < 0 || index > size - 1)   
    179.        {   
    180.            throw new IndexOutOfBoundsException("线性表索引越界");   
    181.        }   
    182.        Node del = null;   
    183.        //如果被删除的是header节点   
    184.        if (index == 0)   
    185.        {   
    186.            del = header;   
    187.            header = header.next;   
    188.            //释放新的header节点的prev引用   
    189.            header.prev = null;   
    190.        }   
    191.        else  
    192.        {   
    193.            //获取删除点的前一个节点   
    194.            Node prev = getNodeByIndex(index - 1);   
    195.            //获取将要被删除的节点   
    196.            del = prev.next;   
    197.            //让被删除节点的next指向被删除节点的下一个节点。   
    198.            prev.next = del.next;   
    199.            //让被删除节点的下一个节点的prev指向prev节点。   
    200.            if (del.next != null)   
    201.            {   
    202.                del.next.prev = prev;   
    203.            }          
    204.            //将被删除节点的prev、next引用赋为null.   
    205.            del.prev = null;   
    206.            del.next = null;   
    207.        }   
    208.        size--;   
    209.        return del.data;   
    210.    }   
    211.    //删除链式线性表中最后一个元素   
    212.    public T remove()   
    213.    {   
    214.        return delete(size - 1);   
    215.    }   
    216.    //判断链式线性表是否为空链表   
    217.    public boolean empty()   
    218.    {   
    219.        return size == 0;   
    220.    }   
    221.    //清空线性表   
    222.    public void clear()   
    223.    {   
    224.        //将底层数组所有元素赋为null   
    225.        header = null;   
    226.        tail = null;   
    227.        size = 0;   
    228.    }   
    229.    public String toString()   
    230.    {   
    231.        //链表为空链表时   
    232.        if (empty())   
    233.        {   
    234.            return "[]";   
    235.        }   
    236.        else  
    237.        {   
    238.            StringBuilder sb = new StringBuilder("[");   
    239.            for (Node current = header ; current != null  
    240.                ; current = current.next )   
    241.            {   
    242.                sb.append(current.data.toString() + ", ");   
    243.            }   
    244.            int len = sb.length();   
    245.            return sb.delete(len - 2 , len).append("]").toString();   
    246.        }   
    247.    }   
    248.    public String reverseToString()   
    249.    {   
    250.        //链表为空链表时   
    251.        if (empty())   
    252.        {   
    253.            return "[]";   
    254.        }   
    255.        else  
    256.        {   
    257.            StringBuilder sb = new StringBuilder("[");   
    258.            for (Node current = tail ; current != null    
    259.                ; current = current.prev )   
    260.            {   
    261.                sb.append(current.data.toString() + ", ");   
    262.            }   
    263.            int len = sb.length();   
    264.            return sb.delete(len - 2 , len).append("]").toString();   
    265.        }   
    266.    }   
    267.       
    268.    public static void main(String[] args)    
    269.    {   
    270.        DuLinkList<String> list = new DuLinkList<String>();   
    271.        list.insert("aaaa" , 0);   
    272.        list.add("bbbb");   
    273.        list.insert("cccc" , 0);   
    274.        //在索引为1处插入一个新元素   
    275.        list.insert("dddd" , 1);   
    276.        //输出顺序线性表的元素   
    277.        System.out.println(list);   
    278.        //删除索引为2处的元素   
    279.        list.delete(2);   
    280.        System.out.println(list);   
    281.        System.out.println(list.reverseToString());   
    282.        //获取cccc字符串在顺序线性表中的位置   
    283.        System.out.println("cccc在顺序线性表中的位置："    
    284.            + list.locate("cccc"));   
    285.        System.out.println("链表中索引1处的元素："    
    286.            + list.get(1));   
    287.        list.remove();   
    288.        System.out.println("调用remove方法后的链表:" + list);   
    289.        list.delete(0);   
    290.        System.out.println("调用delete(0)后的链表:" + list);   
    291.    }   
    292.}