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

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.}