数据结构--双向链表实现（java）

package com.tt.model;
/****
 * 实现一个双向链表
 * @author Gavin
 *
 */
public class LinkList<E> {
    private Node<E> first;
    private Node<E> last;

    private int size;


    public LinkList() {
        this();
    }
    public LinkList(int size) {
        super();
        this.size = size;
    }
    public int size(){
        return this.size;
    }
    /****
     * 在链表末尾添加一个节点
     * @param obj
     */
    public void add(E obj){
        if(this.first == null){
            //链表还没产生时
            this.first = new Node<E>(null,obj,null);
            this.last = this.first;
        }else {
            //链表已经存在了
            this.last.next = new Node<E>(this.last,obj,null);
            this.last = this.last.next;
        }
        this.size++;
    }
    /****
     * 在指定位置添加一个节点
     * @param index
     * @param obj
     * @throws Exception 
     */
    public void add(int index,E obj) throws Exception{
        Node<E> node = node(index);
        Node<E> newNode = new Node<E>(node.pre,obj,node);
        Node<E> pre = node.pre;
        if(pre == null){//当node是头结点的情况
            this.first = newNode;
        }else {
            pre.next = newNode;
        }
        node.pre = newNode;
        this.size++;
    }
    /****
     * 获取指定位置节点
     * @param index
     * @throws Exception 
     */
    public E get(int index) throws Exception{
        Node<E> temp = node(index);
        if(temp == null){
            return null;
        }
        return temp.data;
    }
    /***
     * 移除指定位置节点(返回被移除的数据)
     * @param index
     * @throws Exception 
     * 
     */
    public void remove(int index) throws Exception{
        remove(node(index));
    }
    /****
     * 移除某个对象的节点
     * @param obj
     * @throws Exception 
     */
    public void removeElement(E obj) throws Exception{
        remove(nodeElement(obj));
    }
    /****
     * 移除某个节点
     * @param obj
     */
    private void remove(Node<E> node){
        Node<E> pre = node.pre;
        Node<E> next = node.next;
        if(pre == null){//需要移除的节点没有上一个节点（只能是头结点的情况）
            this.first = next;//将头结点的下一节点，向前移动一格

            if(this.first != null){//有可能当前链表已经空了

                this.first.pre = null;//将头节点的pre赋值为空
            }
        }else if(next == null){//需要移除的节点没有下一个节点（只能是尾结点的情况）

            this.last = pre;//将当前尾结点的前一节点变成尾节点

            this.last.next = null;//将尾节点的next赋值为空
        }else {//一般情况
            pre.next = next;
            next.pre = pre;
        }
        this.size--;
    }
    /****
     * 设置指定位置的值
     * @param index
     * @param obj
     * @throws Exception 
     */
    public void set(int index,E obj) throws Exception{
        node(index).data =obj;
    }
    /***
     * 获取指定位置节点
     * @param index
     * @return
     * @throws Exception 
     */
    private Node<E> node(int index) throws Exception {
        checkIndex(index);
        Node<E> temp = this.first;
        for(int i = ;i<index;i++){
            temp = temp.next;
        }
        return temp;
    }
    /***
     * 根据对象获取位置节点
     * @param index
     * @return
     * @throws Exception 
     */
    private Node<E> nodeElement(E obj) throws Exception {
        Node<E> temp = this.first;
        for(int i = ;i<this.size;i++){
            if(temp.data.equals(obj)){
                return temp;//找到节点跳出
            }
            temp = temp.next;
        }
        return null;
    }

    /***
     * 检查传入的下标是否越界
     * @param index
     * @throws Exception
     */
    private void checkIndex(int index) throws Exception{
        if(index <  || index >= this.size){
            throw new Exception("获取数据错误，数组越界");
        }
    }
    /****
     * 主函数--测试用
     * @param args
     * @throws Exception 
     */
    public static void main(String[] args) throws Exception {
        LinkList list = new LinkList();
        list.add("111");
        list.add("222");
        list.add("333");
        list.add("44444");
        list.add();
        list.add();
        list.remove();
        list.removeElement();
        list.add(,"xxxxxx");
        list.set(, "yyyyyy");
        System.out.println("size === "+list.size());
        for (int i = ;i<list.size();i++) {
            System.out.println("get("+i+") === "+list.get(i));
        }
        //System.out.println("get(99) === "+list.get(99));//越界
    }
}

           

package com.tt.model;

public class Node<E> {
        Node<E> pre;
        Node<E> next;
        E data;

        public Node() {
            super();
        }
        public Node(Node<E> pre, E data ,Node<E> next) {
            super();
            this.pre = pre;
            this.next = next;
            this.data = data;
        }

}