1.3 java代码实现

package com.tingcream.alg.linear;

import java.util.Iterator;

/**
 * 顺序表  api设计 （基于数组）
 * 类名： SequenceList
 * 构造方法： SequenceList(int capacity)//指定容量
 * 成员方法：
 *   public  void clear() 置空顺序表
 *   public  boolean isEmpty()
 *   public int size() 获取线性表长度
 *   public T get(int i);    O(1)
 *   public void add(T t);       O(1)
 *   public void add(int i ,T t);  O(n)
 *   public T remove();   O(1)
 *   public T remove(int i);   O(n)
 *   public int indexOf(T t);  O(n)
 *   public boolean contains(T t);
 *
 * 成员变量 ：
 *   private T[] eles; 存储数据的数组
 *   private int  N;当前线性表的长度
 *
 */
public class SequenceList implements  Iterable{

    private T[] eles;//存储数据的数组 （）
    private int N ;//线性表长度 ，相当于一个指针初始是指向索引0

    public  SequenceList(int capacity){
        this.eles=(T[])new Object[capacity];
        this.N=0;
    }

    //置空顺序表
    public void clear(){
        this.N=0;
    }
    //判断顺序表是否为空
    public boolean isEmpty(){
        return this.N==0;
    }
    //获取顺序表的长度
    public int size(){
        return this.N;
    }

    //获取指定索引的值
    public T  get(int i){
        return eles[i];
    }

    //向顺序表尾部插入元素
    public void add(T t){
        if(N==eles.length){
            resize(2*eles.length);
        }
        this.eles[N++]=t;
        //调用重载的insert方法
       // add(N,t);
    }


    //插入元素
    public void add(int i,T t){
        if(N==eles.length){
            resize(2*eles.length);
        }
        for(int index=N;index>i;index--){
            eles[index]=eles[index--];
        }
        eles[i]=t;
        this.N++;
    }

    //移除最后一个元素
    public T remove(){
        //调用重载的remove方法
       return  remove(N-1);
    }


    //移除一个元素
    public T  remove(int i){
        T value= this.eles[i];
        for(int index=i;index=0;
    }

    //扩容或缩容
    public void resize(int newSize){
        T[] original=eles;
        eles=(T[])new Object[newSize];
        for(int i=0;i iterator() {
        return new Itr();
    }

    //迭代器类
    private class Itr implements Iterator{
        private int cursor;
        public Itr(){
            this.cursor=0;
        }
        @Override
        public boolean hasNext() {
            return  cursor
        }
     }
}

1.4 java测试代码

package com.tingcream.alg.test;

import com.tingcream.alg.linear.SequenceList;

public class SequenceListTest {
    public static void main(String[] args) {
     SequenceList list=new SequenceList(4);
        list.add("aa");
        list.add("bb");
        list.add("cc");
        list.add("dd");
        list.add("ee");

         list.remove(1);

        //遍历
        for(String s: list){
            System.out.println(s);
        }
    }
}

二、链表

2.1 什么是链表

2.2 链表的api设计

2.3 java代码实现

package com.tingcream.alg.linear;

import java.util.Iterator;

/**
 * 链表 api设计
 * 类名： LinkList
 * 构造方法：  LinkList()
 * 成员方法：
 * public void clear()
 * public boolean isEmpty()
 * public int size()
 * public T get(int i)
 * public void add(T t)
 * public void add(int i ,T t)
 * public T  remove()
 * public T  remove(int i)
 * public int indexOf(T t)
 * public boolean contains(T t);
 *
 * 成员内部类：
 *   private class Node 节点类
 * 成员变量：
 *   private Node head;//头结点元素
 *   private int N ; //链表长度
 */
public class LinkList implements Iterable{

    private Node head;//表示头结点
    private int  N;// 链表长度

    //构造方法
    public LinkList(){
        this.head=new Node(null,null);
        this.N=0;
    }

    //清空链表
    public void clear(){
        this.head.next=null;
        this.N=0;
    }

    //获取链表长度
    public int size(){
        return N;
    }

    //判断链表是否为空
    public boolean isEmpty(){
        return N==0;
    }

    //根据位置i获取元素
    public T get(int i){
        Node n=head.next;
        for(int index=0;index=0;
    }


    //反转链表
    public void reverse(){
        if(isEmpty()){
            return ;
        }
        reverse(head.next);
    }

    //把当前反转后的结点对象返回
    private Node reverse(Node current){
        if(current.next==null){
            head.next=current;
            current.next=null;
            return current;
        }
        Node n=  reverse(current.next);
        n.next=current;
        current.next=null;
        return current;
    }

    @Override
    public Iterator iterator() {
        return new Itr();
    }

    //内部类 迭代器
    private  class Itr implements Iterator{
        private Node n;

        public Itr(){
            this.n=head;
        }
        @Override
        public boolean hasNext() {
            return n.next!=null;
        }

        @Override
        public T next() {
             n=n.next;//n指针向后移动一步
            return n.item;
        }
    }

    //内部类 ，表示结点
    private class Node {
        private  T  item;
        private  Node next;
        public  Node(T item,Node next){
            this.item=item;
            this.next=next;
        }
    }
 }

2.4 java测试代码

package com.tingcream.alg.test;

import com.tingcream.alg.linear.LinkList;

 
public class LinkListTest {
    public static void main(String[] args) {
        LinkList  list =new LinkList();

        list.add("aa");
        list.add("bb");
        list.add("cc");
        list.add("dd");

        for(String s: list){
            System.out.println(s);
        }
        System.out.println("bb位置："+list.indexOf("bb"));
        System.out.println("是否包含aa："+list.contains("aa"));

    }
}

ok ..