java实现顺序表、链表、栈 (x)->{持续更新}

1.java实现节点

/**
 * 节点
 * @luminous-xin
 * @param <T>
 */
public class Node<T> {
    T data;
    Node<T> next;
    public Node(Node<T> n){
        next = n;
    }
    public Node(T obj,Node<T> n){
        data = obj;
        next = n;
    }
    public T getData(){
        return data;
    }
    public Node<T> getNext(){
        return next;
    }
}

2.java实现链表

/**
 * 链表
 * @author luminous-xin
 * @param <T>
 */
public class ListLink<T> {
    //头指针
    private Node<T> head;
    //单链表的长度
    private int length;

    //构造一个空的链表
    public ListLink() {
        length = 0;
        head = new Node<T>(null);
    }

    //获取链表头节点的位置
    public Node<T> getHead() {
        return head;
    }

    //在链表中插入一个元素
    public boolean add(T obj, int pos) {
        if (pos < 1 || pos > length + 1) {
            System.out.println("pos值不合法");
            return false;
        }
        int num = 1;
        Node<T> p = head, q = head.next;
        while (num < pos) {
            p = q;
            q = q.next;
            num++;
        }
        p.next = new Node<T>(obj, q);
        length++;
        return true;

    }

    //删除链表中某各元素
    public T remove(int pos) {
        if (isEnpty()) {
            System.out.println("链表为空表");
            return null;
        }
        if (pos < 1 || pos > length + 1) {
            System.out.println("pos值不合法");
            return null;
        }
        int num = 1;
        Node<T> p = head, q = head.next;
        while (num < pos) {
            p = q;
            q = q.next;
            num++;
        }
        p.next = q.next;
        length--;
        return q.data;
    }

    //获取链表中一个元素的值
    public T value(int pos) {
        if (isEnpty()) {
            System.out.println("链表为空表");
            return null;
        }
        if (pos < 1 || pos > length + 1) {
            System.out.println("pos值不合法");
            return null;
        }
        int num = 1;
        Node<T> p = head, q = head.next;
        while (num < pos) {
            p = q;
            q = q.next;
            num++;
        }
        return q.data;
    }

    //在链表中查找一个元素，返回该元素下标的索引
    public int find(T obj) {
        if (isEnpty()) {
            System.out.println("链表为空表");
            return -1;
        }
        int num = 1;

        Node<T> p = head, q = head.next;
        while (q!= null) {
            if (obj.equals(q.data)) {
                return num;
            }
            p = q;
            q = q.next;
            num++;
        }
        return -1;
       /* Node<T> p = head.next;
        while (p != null) {
            if (p.data.equals(obj) == false) {
                p = p.next;
                num++;
            } else break;

        }
        if (p == null) {
            return -1;
        }
        return num;*/
    }

    //更新链表中某各元素
    public boolean modify(T obj, int pos) {
        if (isEnpty()) {
            System.out.println("链表为空表");
            return false;
        }
        if (pos < 1 || pos > length + 1) {
            System.out.println("pos值不合法");
            return false;
        }
        int num = 1;
        Node<T> q = head.next;
        while (num < pos) {
            q = q.next;
            num++;
        }
        q.data = obj;
        return true;
    }

    //判空
    public boolean isEnpty() {
        return length == 0;
    }

    //求链表中数据元素的个数
    public int size() {
        return length;
    }

    //一次访问链表中每个元素并输出
    public void nextOrder() {
        Node<T> q = head.next;
        while (q != null) {
            System.out.println(q.data);
            q = q.next;
        }
    }

    //销毁一个已经存在的链表
    public void clear() {
        length = 0;
        head.next = null;
    }

    public static void main(String[] args) {
        ListLink<Integer> l = new ListLink<>();
        int i;
        int a[] = {23, 56, 12, 49, 35};
        for (i = 0; i < a.length; i++) {
            l.add(a[i], i + 1);
        }
        System.out.println("单链表中的数据元素为：");
        l.nextOrder();
        System.out.println(l.find(5));

    }

3.java实现顺序表

/**
 * 顺序表
 * @author luminous-xin
 * @param <T>
 */
public class SequenceList<T> {
    final int maxSize = 10;           //顺序表中一维数组的长度
    private T[] listArray;             //存储元素的数组对象
    private int length;                 //保存顺序表的当前长度
    public SequenceList(){                   //构造一个空的线性表
        length = 0;
        listArray = (T[])new Object[maxSize];
    }
    public SequenceList(int n){
        if(n <= 0){
            System.out.println("error");
            System.exit(1);
        }
        length = 0;
        listArray = (T[])new Object[n];
    }
    public boolean add(T obj , int pos){                  //在线性表中插入一个新元素
        if(pos < 1 || pos > length + 1){                //检验插入位置的有效性
            System.out.println("pos不合法");
            return false;
        }
        if(length == listArray.length){                 //扩容
            T[] p = (T[])new Object[length*2];
            for (int i = 0; i < length; i++) {
                listArray = p;
            }
        }
        for (int i = length; i > pos; i--) {           //插入
            listArray[i] = listArray[i-1];
        }
        listArray[pos-1] = obj;
        length++;
        return true;
    }
    public T remove(int pos){                               //在线性表中删除一个元素
        if(isEmpty()){
            System.out.println("顺序表为空，无法执行删除操作");
            return null;
        }else{
            if(pos<1 || pos >length){
                System.out.println("pos不合法");
                return null;
            }

            T  x = listArray[pos-1];                          //备份被删除的元素，将其作为返回值返回
            for (int i = pos ; i <= length; i++) {
                listArray[i-1] = listArray[i];
            }
            length++;
            return x;
        }
    }

    public int find(T obj){                      //在线性表中查找一个元素
        if(isEmpty()){
            System.out.println("顺序表为空");
            return -1;
        }else{
            for(int i = 0 ; i <length ; i++){
                if(listArray[i].equals(obj)){
                    return i + 1;                     //返回该元素的位置
                }
            }
            return -1;
        }
    }
    public T value(int pos){                                  //获取线性表中的一个元素
        if(isEmpty()){
            System.out.println("顺序表为空");
        }else{
            if(pos < 1 || pos > length +1){
                System.out.println("pos值不合法");
            }
        }
        return listArray[pos - 1];
    }
    public boolean modify(T obj,int pos){                      //更新线性表中的某各元素
        if(isEmpty()){
            System.out.println("顺序表为空");
            return false;
        }else{
            if(pos < 1 || pos > length  ){
                System.out.println("pos值不合法");
                return false;
            }
        }
        listArray[pos-1] = obj;
        return true;
    }
    public boolean isEmpty(){                              //判空
        return length == 0;
    }
    public int size(){                              //求线性表中数据元素的个数
        return length;
    }
    public void nextOrder(){                      //一次访问栈中的每个元素并输出
        for(int i = 0 ; i< length; i++ ){
            System.out.println(listArray[i]);
        }
    }
    public void clear(){                       //销毁一个已经存在的线性表
        length = 0;
    }


}

4.链表的应用，合并两个有序链表

public class Chap2_2 {
    public static <T extends Comparable> void MergeList_L(ListLink<T> la, ListLink<T> lb ,ListLink<T> lc){
        Node<T> pa,pb,pc;
        pa = la.getHead().next;
        pb = lb.getHead().next;
        pc = lc.getHead();

        while(pa != null && pb != null){
            if(pa.data.compareTo(pb.data)<0){
                pc.next = pa;
                pc = pa ;
                pa = pa.next;
            }else{
                pc.next = pb;
                pc = pb;
                pb = pb.next;
            }

            while (pa != null){
                pc.next = pa;
                pc =  pc.next;
                pa = pa.next;
            }
            while (pb != null){
                pc.next = pb;
                pc = pb;
                pb = pb.next;
            }
            la.clear();
            lb.clear();
        }
    }
    public static void main(String[] args) {
        int i,j,k = 0;
        int[] b = {12,23,35,49,56};
        int[] a = {10,15,20};
        ListLink<Integer> la = new ListLink<>();
        ListLink<Integer> lb = new ListLink<>();
        ListLink<Integer> lc = new ListLink<>();
        for ( i = 0; i < a.length; i++) {
            la.add(a[i],i+1);
        }
        System.out.println("单链表a中的元素为：");
        la.nextOrder();
        for (j = 0; j < b.length; j++) {
            lb.add(b[j],j+1);
        }
        System.out.println("单链表b中的数据元素为：");
        lb.nextOrder();
        MergeList_L(la,lb,lc);
        System.out.println("单链表c中的元素为：");
        lc.nextOrder();
    }
}

5.java实现顺序栈

/**
 * 顺序栈
 * @author luminous-xin
 * @param <T>
 */
public class SequenceStack<T> {
    final int maxSize = 10;
    private T[] stackArray;
    private int top;
    //各方法的具体实现后有详细描述
    public SequenceStack(){
        top = -1;
        stackArray = (T[])new Object[maxSize];
    }
    public SequenceStack(int n){
        if(n<=0){
            System.out.println("数组长度要大于零，否则退出程序运行！");
            System.exit(1);
        }
        top = -1;
        stackArray = (T[])new Object[n];
    }
    //在栈顶位置插入一个新元素
    public void push(T obj){
        if(top == stackArray.length-1){
            T[] p = (T[])new Object[top*2+2];
            for (int i = 0; i <= top; i++){
                p[i] = stackArray[i];
            }
            stackArray = p;
        }

        top++;
        stackArray[top] = obj;
    }
    //删除栈顶元素
    public T pop(){
        if(top == -1) {
            System.out.println("数据栈已空，无法删除元素");
            return null;
        }
        top--;
        return stackArray[top+1];
    }
    //取栈顶数据元素
    public T getHead(){
        if (top == -1){
            System.out.println("数据栈已空，无法删除元素");
            return null;
        }
        return stackArray[top];
    }
    //判断当前栈是否为空
    public boolean isEmpty(){
        return top == -1;
    }
    //求出栈中元素的个数
    public int size(){
        return top +1;
    }
    //依次访问栈中元素并输出
    public void nextOrder(){
        for(int i = top ; i >= 0;i--){
            System.out.println(stackArray[i]);
        }
    }
    //销毁一个已经存在的栈
    public void clear(){
        top = -1;
    }
}

 6.java实现链栈

/**
 * 链栈
 * @luminous-xin
 * @param <T>
 */
public class LinkStack<T> {
    private Node<T> top;   //栈顶指针
    private int length;     //存储栈的长度
    public LinkStack(){     //构造一个空的栈
        length = 0;
        top = null;
    }
    public void push(T obj){        //入栈
        top = new Node<T>(obj,top);
        length++;
    }
    public T pop(){                 //出栈
        if(top == null){
            System.out.println("栈已空，无法删除");
            return null;
        }
        T x = top.data;
        top = top.next;
        length--;
        return x;
    }
    public T getHead(){             //取栈顶元素
        if(top == null){
            System.out.println("栈已空，无法删除");
            return null;
        }
        return top.data;
    }
    public int size(){              //求出栈中元素的个数
        return length;
    }
    public boolean isEmpty(){       //判断栈是否为空
        if (top ==null){
            return true;
        }
        return false;
    }
    public void nextOrder(){        //便利栈
        Node<T> p = top;
        while (p != null){
            System.out.println(p.data);
            p = p.next;
        }
    }

    public void clear(){            //销毁一个栈
        top = null;
    }
}

 7.java实现顺序链表

import org.omg.CORBA.Object;

/**
 * 循环队列
 * @author luminous
 * @param <T>
 */
public class SequenceQueue<T> {
    final int maxSize = 10;
    private T queueArray[];
    private int front, rear;

    public SequenceQueue() {
        rear = front = 0;
        queueArray = (T[]) new Object[maxSize];
    }

    public void enQueue(T obj) {                            //入队
        if ((rear + 1) % queueArray.length == front) {
            T[] p = (T[]) new Object[queueArray.length * 2];
            if (rear == ((T[]) queueArray).length) {
                for (int i = 0; i <= rear; i++) {
                    p[i] = queueArray[i];
                }
            } else {
                int i,j = 1;
                for (i = front + 1; i<queueArray.length;i++,j++)
                    p[j] = queueArray[i];
                for (i = 0;i<= rear ; i++,j++)
                    p[j] = queueArray[i];
                front = 0;
                rear = queueArray.length-1;
            }
            queueArray = p;
        }
        rear = (rear+1)%queueArray.length;
        queueArray[rear] = obj;
    }
    public T DeQueue(){                             //出队
        if(isEmpty()){
            System.out.println("队列已空，无法出队！");
            return null;
        }
        front = (front +1)%queueArray.length;
        return queueArray[front];

    }
    public T getTop(){                                  //取出头元素
        if(isEmpty()){
            System.out.println("队列已空，无法读取元素！");
            return null;
        }
        return queueArray[(front+1)%queueArray.length] ;
    }
    public boolean isEmpty(){                   //队列的非空队列
        return front==rear;
    }
    public int size(){                      //求队列长度
        return (rear - front +queueArray.length)%queueArray.length;
    }
    public void nextOrder(){            //遍历队列
        int i,j = front ;
        for (i = 1; i < size(); i++) {
            j = (j+1)%queueArray.length;
            System.out.println(queueArray[j]);

        }
    }
    public void clear(){       //清空队列
            front = rear =0;
    }
}