手动实现LinkedList

1.首先实现一个node类

 1 package text;
 2 
 3 
 4 //用来表示一个节点
 5 public class Node{
 6      Node previous;//注意类型
 7      Object obj;
 8      Node next;
 9     
10     public Node(){
11         
12     }
13     public Node(Node previous,Object obj,Node next){//构造方法
14         super();
15         this.previous = previous;
16         this.obj=obj;
17         this.next= next;
18         
19     }
20     public Object getPrevious(){
21         return previous;
22     }
23     public void setPrevious(Node previous){
24         this.previous= previous;
25     }
26     
27     public Object getObj(Object obj){
28         return obj;
29     }
30     public void setObj(Object obj){
31         this.obj=obj;
32     }
33     public Node getNext(){
34         return next;
35     }
36     public void setNext(Node next){
37         this.next=next;
38     }
39     
40 }

2.实现linkedList

  1 package text;
  2 import java.util.LinkedList;
  3 
  4 
  5 public class SxtLinkedList{
  6     private Node first;
  7     private Node last;
  8     private int size;
  9     
 10     public void add(Object obj){
 11         Node n= new Node();
 12         if(first==null){
 13             n.setPrevious(null);
 14             n.setObj(obj);
 15             n.setNext(null);
 16             
 17             first=n;
 18             last=n;
 19         }
 20         else{
 21             //直接往last接待你后增加新的节点
 22             n.setPrevious(last);//设置前面的指向
 23             n.setObj(obj);
 24             n.setNext(null);//设置后面的指向
 25             
 26             last.setNext(n);//将与前面的节点关联
 27             last=n;//设置后一个节点
 28         }
 29         size++;//链表长度加一
 30     }
 31     public int size(){
 32         return size;
 33     }
 34     
 35     private void rangeCheck(int index){//越界函数
 36         if(index<0||index>=size){//size表示长度,真实的下标是长度减一，所以当下标位长度时就已经越界
 37             try{
 38                 throw new Exception();
 39                 
 40             }catch(Exception e){
 41                 e.printStackTrace();
 42             }
 43         }
 44     }
 45     public Object get(int index){
 46         rangeCheck(index);//判断是否越界
 47         
 48         Node temp=node(index);//下面的node方法
 49         if(temp!=null){
 50             return temp.obj;
 51             
 52         }
 53         return null;
 54         
 55     }
 56     
 57 /**
 58  * publi Node node(int index){
 59  *         Node temp=null;
 60  *             if(first!=null){
 61  *                 temp=first;
 62  *              for(int i=0;i<index;i++){
 63  *                  temp=temp.next;
 64  *              }
 65  *             }
 66  * return temp;
 67  * }
 68  * 
 69  * @param index
 70  * @return
 71  */
 72     
 73     public Node node(int index){
 74         Node temp= null;
 75         if(first!=null){
 76             if(index<(size>>1)){
 77                 temp=first;
 78                 for(int i=0;i<index;i++){
 79                     temp=temp.next;
 80                 }
 81             }else{
 82                 temp=last;
 83             for(int i=size-1;i>index;i--){
 84                 temp=temp.previous;
 85             }
 86             }
 87         }
 88         return temp;
 89     }
 90     public void remove(int index){//移除某个节点
 91         Node temp= node(index);
 92         if(temp!=null){
 93             Node up=temp.previous;//上一个节点
 94             Node down=temp.next;//下一个节点
 95             up.next=down;
 96             down.previous=up;
 97             size--;
 98         }
 99     }
100     public void add(int index,Object obj){//插入
101         Node temp=node(index);
102         
103         Node newNode = new Node();
104         newNode.obj=obj;
105         if(temp!=null){
106             Node up=temp.previous;
107             up.next=newNode;
108             newNode.previous=up;
109             
110             newNode.next=temp;
111             temp.previous = newNode;
112             
113             size++;
114         }
115     }
116     
117     public static void main(String[] args){
118         SxtLinkedList list= new SxtLinkedList();
119         list.add("aaa");
120         list.add("bbb");
121         list.add(1,"BBBB");
122         list.add("ccc");
123         list.remove(1);
124         System.out.println(list.get(2));
125     }
126     
127 }

双向链表的插入示意图