链式存储及实现

单链表：

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package com.mycompany.data.structure.line;
/**
 *单链表
 * @author wyman
 */
public class SingleLinkedList<T> {
    T data;
    SingleLinkedList next;
    public SingleLinkedList<T> initList() {
        return new SingleLinkedList<T>(); //To change body of generated methods, choose Tools | Templates.
    }
    //over 不知道对不对
    public SingleLinkedList<T> initList(int i) {
        SingleLinkedList Head = new SingleLinkedList<T>();
        SingleLinkedList tmp = Head;
        while (i > 0) {
            tmp.next = new SingleLinkedList();
            tmp = tmp.next;
            i--;
        }
        return Head; //To change body of generated methods, choose Tools | Templates.
    }
    //over
    public static void clearList(SingleLinkedList head) {
        head.next = null; //To change body of generated methods, choose Tools | Templates.
    }
    //over
    public static boolean listEmpty(SingleLinkedList head) {
        if (null != head.next) {
            return false;
        }
        return true;
    }
    //over 
    public int locateElem(SingleLinkedList head, T t) {
        int i = 1;
        SingleLinkedList node = head.next;
        while (true) {
            if (node == null) {
                return 0;
            }
            if (node == t) {
                return i;
            }
            node = node.next;
            i++;
        }
    }
    //over 
    public T getElem(SingleLinkedList head, int i) {
        SingleLinkedList node = head.next;
        while (i > 1) {
            node = node.next;
            if (null == node) {
                break;
            }
            i--;
        }
        return (T) node;
    }
    //over
    public T priorElem(SingleLinkedList head, T t) {
        SingleLinkedList node = head.next;
        if (node == t) {
            return null;
        }
        while (true) {
            if (node == null) {
                return null;
            }
            if (node.next == t) {
                return (T) node;
            }
            node = node.next;
        }
    }
    //over
    public T nextrElem(SingleLinkedList head, T t) {
        SingleLinkedList node = head.next;
        while (true) {
            if (node == t) {
                return (T) node.next;
            }
            if (node.next == null) {
                return null;
            }
            node = node.next;
        }
    }
    public boolean listInsert(SingleLinkedList head, int i, T t) {
        if (i < 1) {
            return false;
        }
        SingleLinkedList node = head;
        for (int index = 1; index < i; index++) {
            if (node.next == null) {
                return false;
            }
            node = node.next;
        }
        SingleLinkedList after_insert_node = node.next;
        SingleLinkedList insertNode = (SingleLinkedList) t;
        node.next = insertNode;
        insertNode.next = after_insert_node;
        return true;
    }
    public T listDelete(SingleLinkedList head, int target) {
        SingleLinkedList node = head;
        int node_index = 0;
        while (true) {
            if (null == node) {
                return null;
            }
            if (node_index == target - 1) {
                SingleLinkedList deleteNode = node.next;
                node.next = deleteNode.next;
                return (T) deleteNode;
            }
            node = node.next;
            node_index++;
        }
    }
    public void listTraverse() {
        throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
    }
    public int getSize(SingleLinkedList head) {
        int i = 0;
        SingleLinkedList node = head.next;
        while (true) {
            if (null == node) {
                break;
            }
            i++;
            node = node.next;
        }
        return i;
    }
    public void DestoryList(SingleLinkedList head) {
        throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
    }
}

静态链表：数组表示的单链表

/**
 *静态链表（用数组存取）
 * @author wyman
 */
public class StaticListElement {
    int cur;
    Object data;
    public StaticListElement() {
    }
    public StaticListElement(int cur, Object data) {
        this.cur = cur;
        this.data = data;
    }
}
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package com.mycompany.data.structure.line;
/**
 *
 * @author wyman
 */
public class StaticList {
    StaticListElement[] sle;
    int size;
    //over 不
    public StaticList initList(int i) {
        StaticList Slist = new StaticList();
        Slist.sle = new StaticListElement[i];
        Slist.size = i;
        return Slist;
    }
    //over
    public static void clearList(StaticList Slist) {
        Slist.size = 0; //To change body of generated methods, choose Tools | Templates.
    }
    //over
    public static boolean listEmpty(StaticList Slist) {
        if (0 < Slist.size) {
            return false;
        }
        return true;
    }
    //over 
    public int locateElem(StaticList Slist, StaticListElement t) {
        for (int i = 0; i < Slist.size; i++) {
            if (t.data == Slist.sle[i].data) {
                return Slist.sle[i].cur;
            }
        }
        return 0;
    }
    //over 
    public StaticListElement getElem(StaticList Slist, int k) {
        if (k <= 0 || k > size) {
            return null;
        }
        StaticListElement head = Slist.sle[0];
        StaticListElement tmp = head;
        while (tmp.cur != 0) {
            if (k == tmp.cur) {
                return tmp;
            }
            tmp = Slist.sle[tmp.cur];
        }
        return null;
    }
    //over
    public StaticListElement priorElem(StaticList Slist, StaticListElement t) {
        for (int i = 0; i < Slist.size; i++) {
            if (t.data == Slist.sle[i].data) {
                return getElem(Slist, Slist.sle[i].cur - 1);
            }
        }
        return null;
    }
    //over
    public StaticListElement nextrElem(StaticList Slist, StaticListElement t) {
        for (int i = 0; i < Slist.size; i++) {
            if (t.data == Slist.sle[i].data) {
                return getElem(Slist, Slist.sle[i].cur + 1);
            }
        }
        return null;
    }
    public boolean listInsert(StaticList Slist, int i, StaticListElement t) {
        if (i < 1 || i > Slist.size + 1) {
            return false;
        }
        //若空间满了创建一个新的数组
        StaticListElement before_node = getElem(Slist, i - 1);
        StaticListElement after_node = getElem(Slist, i);
        Slist.sle[i] = t;
        t.cur = before_node.cur;
        before_node.cur = i;
        return true;
    }
    public StaticListElement listDelete(StaticList Slist, int i) {
         if (i < 1 || i > Slist.size ) {
            return null;
        }
       StaticListElement target_node = getElem(Slist, i - 1);
       StaticListElement pre_node=priorElem(Slist, target_node);
       pre_node.cur=target_node.cur;
        return target_node;
    }
    public void listTraverse() {
        throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
    }
    public int getSize(StaticList Slist) {
        return Slist.size-1;
    }
    public void DestoryList(SingleLinkedList head) {
        throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
    }
}

循环链表：

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package com.mycompany.data.structure.line;
/**
 *
 * @author wyman
 */
public class circularLinkedList<T> {
    T data;
    circularLinkedList next;
    public circularLinkedList<T> initList() {
        return new circularLinkedList<T>(); //To change body of generated methods, choose Tools | Templates.
    }
    //over 不知道对不对
    public circularLinkedList initList(int i) {
        circularLinkedList head = new circularLinkedList<T>();
        circularLinkedList tmp = head;
        while (i > 0) {
            tmp.next = new circularLinkedList();
            tmp = tmp.next;
            i--;
        }
        tmp.next = head;
        return head; //To change body of generated methods, choose Tools | Templates.
    }
    //over
    public static void clearList(circularLinkedList head) {
        head.next = null; //To change body of generated methods, choose Tools | Templates.
    }
    //over
    public static boolean listEmpty(circularLinkedList head) {
        if (null != head.next) {
            return false;
        }
        return true;
    }
    //over 
    public int locateElem(circularLinkedList head, T t) {
        int i = 1;
        circularLinkedList node = head.next;
        while (true) {
            if (node == head) {
                return 0;
            }
            if (node == t) {
                return i;
            }
            node = node.next;
            i++;
        }
    }
    //over 
    public T getElem(circularLinkedList head, int i) {
        circularLinkedList node = head.next;
        while (i > 1) {
            node = node.next;
            if (head == node) {
                break;
            }
            i--;
        }
        return (T) node;
    }
    //over
    public T priorElem(circularLinkedList head, T t) {
        circularLinkedList node = head.next;
        if (node == t && node == head) {
            return null;
        }
        while (true) {
            if (node == head) {
                return null;
            }
            if (node.next == t) {
                return (T) node;
            }
            node = node.next;
        }
    }
    //over
    public T nextrElem(circularLinkedList head, T t) {
        circularLinkedList node = head.next;
        if (node == head) {
            return null;
        }
        while (true) {
            if (node == t) {
                return (T) node.next;
            }
            if (node.next == head) {
                return null;
            }
            node = node.next;
        }
    }
    public boolean listInsert(circularLinkedList head, int i, T t) {
        if (i < 1) {
            return false;
        }
        circularLinkedList node = head;
        for (int index = 1; index < i; index++) {
            if (node.next == head) {
                return false;
            }
            node = node.next;
        }
        circularLinkedList after_insert_node = node.next;
        circularLinkedList insertNode = (circularLinkedList) t;
        node.next = insertNode;
        insertNode.next = after_insert_node;
        return true;
    }
    public T listDelete(circularLinkedList head, int target) {
        circularLinkedList node = head;
        int node_index = 0;
        while (node.next != head && node_index < target - 1) {
            node = node.next;
            node_index++;
        }
        if (node_index == target - 1) {
            circularLinkedList deleteNode = node.next;
            node.next = deleteNode.next;
            return (T) deleteNode;
        }
        return null;
    }
    public void listTraverse() {
        throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
    }
    public int getSize(circularLinkedList head) {
        int i = 0;
        circularLinkedList node = head.next;
        while (true) {
            if (head == node) {
                break;
            }
            i++;
            node = node.next;
        }
        return i+1;
    }
    public void DestoryList(SingleLinkedList head) {
        throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
    }
}

双向链表：

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package com.mycompany.data.structure.line;
/**
 *
 * @author wyman
 */
public class DuLinkList<T> {
      T data;
    DuLinkList next;
    DuLinkList pre;
    public DuLinkList<T> initList() {
        return new DuLinkList<T>(); //To change body of generated methods, choose Tools | Templates.
    }
    //over 不知道对不对
    public DuLinkList initList(int i) {
        DuLinkList head = new DuLinkList<T>();
        DuLinkList tmp = head;
        while (i > 0) {
            DuLinkList node=new DuLinkList();
            node.pre=tmp;
            tmp.next = node;
            tmp = tmp.next;
            i--;
        }
        tmp.next = head;
        return head; //To change body of generated methods, choose Tools | Templates.
    }
    //over
    public static void clearList(DuLinkList head) {
        head.next = head;
        head.pre=head;//To change body of generated methods, choose Tools | Templates.
    }
    //over
    public static boolean listEmpty(DuLinkList head) {
        if (head != head.next) {
            return false;
        }
        return true;
    }
    //over 
    public int locateElem(DuLinkList head, T t) {
        int i = 1;
        DuLinkList node = head.next;
        while (true) {
            if (node == head) {
                return 0;
            }
            if (node == t) {
                return i;
            }
            node = node.next;
            i++;
        }
    }
    //over 
    public T getElem(DuLinkList head, int i) {
        DuLinkList node = head;
        while (i > 0) {
            node = node.next;
            if (head == node) {
                break;
            }
            i--;
        }
        return (T) node;
    }
    //over
    public T priorElem(DuLinkList head, T t) {
      return (T) ((DuLinkList)t).pre;
    }
    //over
    public T nextrElem(DuLinkList head, T t) {
        return (T) ((DuLinkList)t).next;
    }
    public boolean listInsert(DuLinkList head, int i, T t) {
        if (i < 1) {
            return false;
        }
        DuLinkList node = head;
        for (int index = 1; index < i; index++) {
            if (node.next == head) {
                return false;
            }
            node = node.next;
        }
        DuLinkList after_insert_node = node.next;
        DuLinkList insertNode = (DuLinkList) t;
        insertNode.pre=node;
        node.next = insertNode;
        insertNode.next = after_insert_node;
        after_insert_node.pre=insertNode;
        return true;
    }
    public T listDelete(DuLinkList head, int target) {
        DuLinkList node = head;
        int node_index = 0;
        while (node.next != head && node_index < target - 1) {
            node = node.next;
            node_index++;
        }
        if (node_index == target - 1) {
            DuLinkList deleteNode = node.next;
            node.next = deleteNode.next;
            deleteNode.next.pre=node;
            return (T) deleteNode;
        }
        return null;
    }
    public void listTraverse() {
        throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
    }
    public int getSize(DuLinkList head) {
        int i = 0;
        DuLinkList node = head.next;
        while (true) {
            if (head == node) {
                break;
            }
            i++;
            node = node.next;
        }
        return i+1;
    }
    public void DestoryList(SingleLinkedList head) {
        throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
    }
}