java 手工實現LinkedList容器

泛型、創建鏈表、重寫打印、返回索引位置的值、返回指定節點、刪除節點、指定位置添加節點、判斷索引異常

需要兩個類，一個表示節點信息和指針，一個表示節點位置并實現鏈表

第一個不同文件類：

public class node {

    node next;  //指向下一個節點
    node pre;   //指向上一個節點
    Object obs;  //節點數據

    public node(Object obs)
    {
        this.obs=obs;
    }

}

第二個實現類：

package hell;
public class test<E> {
    private node first; //節點首位置
    private node last;  //節點實時位置
    private int size;  //記錄節點個數

public void add(E obs) //添加元素添加鏈表
{
    node p=new node(obs);
    if(first==null)    //如果是第一個元素
    {
        first=p;      //定位first
        last=p;       //定位實時last
    }
    else
    {
        last.next=p;   //將第二個節點與第一個節點雙向鏈接，并使得第二個節點指向null
        p.pre=last;
        p.next=null;
        last=p;

    }
    size++;

}
public void checkIndex(int index) //判斷索引異常
{
    if(index<0||index>=size)
    {
        throw new RuntimeException("索引異常");
    }
}
public E get(int index) //返回索引的值，根據索引大小來判斷查找順序
{
    checkIndex(index);
    node p;
    if(index>=size/2)
    {
        p=last;
        for(int i=size-1;i>index;i--)
        {
            p=p.pre;
        }
    }
    else
    {
        p=first;
        for(int i=0;i<index;i++)
        {
            p=p.next;
        }
    }
    return (E)p.obs;
}

public node getNode(int index)  //返回指定節點
{
    checkIndex(index);
    node p=first;
    for(int i=0;i<index;i++)
    {
        p=p.next;
    }
    return p;

}
public void rem(int index)//刪除節點
{
    checkIndex(index);
    node p=getNode(index);
    node up=p.pre;
    node down=p.next;
    if(up!=null)    //判斷up和down是否為空，不能讓空指針指向其他，只適合一般節點和尾節點
    {
        up.next=down;  //刪除尾節點時，使得尾節點的上一個節點指向空，從而刪除尾節點
    }
    if(down!=null)
    {
        down.pre=up;  //刪除頭節點時，只是讓頭節點的下一個節點指向上一個節點為空，但頭節點
                    //依舊能指向下一個節點，故無法刪除
    }
    if(index==0) //刪除頭節點
    {
        first=p.next;
    }
    if(index==size-1)
    {
        last=null;
    }

}
public void add(int index,E obs)//指定位置添加節點
{
    checkIndex(index);
    node newnode=new node(obs);
    node p=getNode(index);
    node up=p.pre;

    up.next=newnode;
    newnode.pre=up;
    newnode.next=p;
    up=newnode;

}
public String toString()//重寫toString方法
{
    StringBuilder s=new StringBuilder();
    s.append("[");
    node p=first;
    while(p!=null)
    {
        s.append(p.obs+",");
        p=p.next;
    }
    s.setCharAt(s.length()-1, ']');
    return s.toString();

}

public static void main(String[]args)
{
    test<String> link=new test<>();
    link.add("a");
    link.add("b");
    link.add("c");
    System.out.println(link);
    System.out.println(link.get(2));
    node p=link.getNode(2);
    System.out.println(p.obs);
    link.rem(0);
    System.out.println(link);
    link.add(3,"d");
    System.out.println(link);
}

}