8535.com-新浦京娱乐场官网|欢迎您

实现一个简单的LinkedList——高淇JAVA300讲笔记之

来源:http://www.dnamique.com 作者:计算机网络 人气:72 发布时间:2019-10-07
摘要:实现一个简单的LinkedList——高淇JAVA300讲笔记之LinkedList,linkedlistjava300    老高的这部分代码其实写的比较粗糙,比如头结点和尾节点都考虑的不是很全面,不过敲一遍用来理解LinkedL

实现一个简单的LinkedList——高淇JAVA300讲笔记之LinkedList,linkedlistjava300

    老高的这部分代码其实写的比较粗糙,比如头结点和尾节点都考虑的不是很全面,不过敲一遍用来理解LinkedList的原理还是不错的。实现了add()、get()、size()、remove()等方法。

    LinkedList也是有序,可重复的。底层实现是链表,线程不安全,效率高。查询慢,修改、插入、删除快。

    在写的时候在纸上画几个节点会比较好理解一点。

    

    先是Node类,用来表示一个节点:

 1 package cn.bjsxt.collection;
 2 
 3 //用来表示一个节点
 4 public class Node {
 5     Node previous;  //上一个节点
 6     Object obj;  //该节点的对象
 7     Node next;  //下一个节点
 8     
 9     //无参构造器
10     public Node() {
11     }
12     
13     //有参构造器
14     public Node(Node previous, Object obj, Node next) {
15         super();
16         this.previous = previous;
17         this.obj = obj;
18         this.next = next;
19     }
20 
21     /**
22      * 以下是getter和setter方法
23      * @return
24      */
25     public Node getPrevious() {
26         return previous;
27     }
28 
29     public void setPrevious(Node previous) {
30         this.previous = previous;
31     }
32 
33     public Object getObj() {
34         return obj;
35     }
36 
37     public void setObj(Object obj) {
38         this.obj = obj;
39     }
40 
41     public Node getNext() {
42         return next;
43     }
44 
45     public void setNext(Node next) {
46         this.next = next;
47     }
48 
49 }

 

    然后是我们自己写的LinkedList类:

  1 package cn.bjsxt.collection;
  2 
  3 public class SxtLinkedList {
  4     private Node first;  //头节点
  5     private Node last;  //尾节点
  6     
  7     private int size;  //LinkedList的大小
  8     
  9     //增加一个节点    
 10     public void add(Object obj) {
 11         Node n = new Node();
 12         
 13         //如果没有第一个节点
 14         if(first == null) {
 15             n.setPrevious(null);
 16             n.setObj(obj);
 17             n.setNext(null);
 18             
 19             first = n;
 20             last = n;  //这个节点既是第一个也是最后一个
 21         } else {
 22             //直接往last节点后增加新的节点
 23             n.setPrevious(last);  //把最后一个节点设为新节点的上一个节点
 24             n.setObj(obj);
 25             n.setNext(null);
 26             
 27             last.setNext(n);  //新节点设为当前最后一个节点的下一个节点
 28             
 29             last = n;  //新节点成为最后一个节点
 30     
 31         }
 32         size++;
 33     }
 34     
 35   //在指定位置插入一个新对象
 36     public void add(int index, Object obj) {
 37         rangeCheck(index);  //检查数组下标是否越界
 38         Node temp = node(index);  //指定位置上的节点
 39         
 40         Node newNode = new Node();
 41         newNode.obj = obj;
 42         
 43         if(temp != null) {
 44             Node up = temp.previous;  //原节点的上一个节点
 45             up.next = newNode;  //新节点设为上一个节点的下一个节点
 46             newNode.previous = up;  //上一个节点设为新节点的上一个节点
 47             
 48             newNode.next = temp;  //原节点设为新节点的下一个节点
 49             temp.previous = newNode;  //新节点设为原节点的上一个节点
 50             
 51             size++;
 52         }
 53     }
 54     
 55     //返回链表的大小
 56     public int size() {
 57         return size;
 58     }
 59     
 60     //数组下标越界检查
 61     private void rangeCheck(int index) {
 62         if(index<0 || index>=size) {
 63             try {
 64                 throw new Exception();
 65             } catch (Exception e) {
 66                 e.printStackTrace();
 67             }
 68         }
 69     }
 70     
 71     //返回指定位置的元素
 72     public Object get(int index) {
 73         rangeCheck(index);  //检查数组下标是否越界
 74         
 75         Node temp = node(index);
 76         if(temp != null) {
 77             return temp.obj;
 78         }
 79         return null;
 80     }
 81     
 82     //返回指定位置的节点Node对象
 83     public Node node(int index) {
 84         Node temp = null;
 85         if(first != null) {
 86             temp = first;
 87             for(int i=0;i<index;i++) {
 88                 temp = temp.next;
 89             }
 90         }
 91         return temp;
 92     }
 93     
 94     
 95     //删除指定位置上的节点
 96     public void remove(int index) {
 97         Node temp = node(index);
 98         
 99         if(temp != null) {
100             Node up = temp.previous;
101             Node down = temp.next;
102             up.next = down;
103             down.previous = up;
104             size--;
105         }
106         
107         
108     }
109     
110     public static void main(String[] args) {
111         SxtLinkedList list = new SxtLinkedList();
112         list.add("aaa");
113         list.add("bbb");
114         list.add(1,"BBBB");
115         System.out.println(list.size());
116         System.out.println(list.get(2));
117 //        list.remove(1);
118         System.out.println(list.get(1));
119     }
120     
121     
122 }

老高的这部分代码其实写的比较粗糙,比如头结点和尾节点都考虑的...

本文由8535.com-新浦京娱乐场官网|欢迎您发布于计算机网络,转载请注明出处:实现一个简单的LinkedList——高淇JAVA300讲笔记之

关键词:

最火资讯