java 线性表-------单链表表示形式（源代码）

╰半夏微凉° 2023-10-13 16:08 18阅读 0赞

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