数据结构(data structure)（1）链表和线性表

 类和对象

对象将数据和操作打包在一起，类描述了这一切
用构造器创建(实例化)对象
类和类之间的关系
-关联（组合，聚集）
-泛化

private class Student{
    protected String name;
    protected int age;
    protected int ability;

    public Student(String name,int age){
        this.name=name;
        this.age=age;
    }
4

    public  void study(){
        ability++;
    }

    public String toString(){
         return "Student{"+"name="+name+'\''+",age"+age+",ability="+ability+'}';
    }

    public boolean equals(Object o){
        if(this==o)return true;
        if(o==null||getClass()!=o.getClass())return false;

        Student student =(Student)o;
        return name.equals(student.name);
    }

    public static void main(String[] args){
          Student stu1=new Student();
          Student stu2=new Student();

          System.out.println(stu1.toString());
          System.out.println(stu1.equal(stu2));
    }
}

关于继承

祖先类Object
方法重写
toString方法
equals方法

public class CleverStudent extends Student{
    public CleverStudent(String name,int age){

    super(name,age);
    }

    public void study(){
    super.study();
    super.study();
    }

    public void study(int s){
        ability+=s;
    }
}


Comparable接口，比较大小
Comparator接口,比较器
Cloneable接口，克隆
seriazable接口，可序列化，io接入网路需要

数据结构基本概念

数据(data)
数据元素(data element)
数据对象(data object)

数据是一种泛指

数据对象
数据元素
数据项

（数据对象）student
{
    （name（数据项）,age）   (数据元素)
}

数据结构(data structure)

辑结构
集合:元素罗列在一起
线性结构:元素前后相继(一一对应)
树形结构:(元素存在一对多的关系)
图结构或网状结构：元素之间存在多对多的结构

存储结构
-顺序存储:地址连续，用数组
-链式存储:地址不连续，用指针(引用，面向对象)


Create建立
Destroy消除
Delete删除
Insert插入
Access访问
Modify修改
Sort排序
Search查找
增删改查排历

 列表:顺序表和链表

定义列表接口
用数组实现列表-MyArrayList
实现列表
Java List API

 顺序表

public interface MyList{

    //新增一个元素
    void add(Object element);
    //删除相同元素
    void delete(Object element)
    //根据索引删除元素
    void delete(int index);

    //将指定索引位置的·元素替换成新元素
    void update(int index,Object newElement);

    //当前列表中是否含有target元素
    boolean contains(Object target);

    //返回指定索引处元素
    Object indexOf(int index);

}

    public class MyArrayList implements MyList{

    private int size=0//元素个数

    private int capacity;//容量

    public MyArrayList(int capacity){
        this.capacity=capacity;
        elements=new Object[capacity];
}
          //新增一个元素
    void add(Object element){
        if(size==capacity)//扩容
        {
         capacity*=2;//增加一倍的容量
          Object[] newArr=new Object[capacity];//把旧的柜子扔掉
           newArr[i]=elements[i];
           }
        elements[size++]=element;
    }

    //删除相同元素
    void delete(Object element){
    int index=indexOf(element);
    if(index>=0){
    delete(index);
    }

    }
    //根据索引删除元素
    void delete(int index){
    for(int i=index;i<size;i++){
        elements[i]=elements[i+1];
    }
    size--;

    }
    //将指定索引位置的·元素替换成新元素
    void update(int index,Object newElement){
    elemenyts[index]=newElement;
    }

    //当前列表中是否含有target元素
    boolean contains(Object target){

    }

    //返回指定索引处元素
    Object at(int index){
        return elements[index];
    }

     //查找element的索引，如果没有返回-1
    Object indexOf(Object element){
    for(int i=0;i<size;i++){
    if(elements[i].equals(element))
        return i;
    }

    return -1;
    }
    public String toString(){
    StringgBuilder sb=new StringBuilder("[");
        for(int i=0;i<size;i++){
        sb.append(elements[i]+(i==size-1?"":","));
        }
        sb.appen("]");
        return sb.toString();
    }

    }


publi class MyArraylistTest{
    public  void add() throw Exception{
    MyArrayList list=new MyArrayList();
    list.add("nike");
    List.add("addidiaos");
    List.add("nb");
    }


}

单链表

head头节点,Node[data,point]->[data,point]->[]->[]

public class ListNode{
    private Object data;
    private ListNode next;

    public ListNode(data){
    this.data=data;
    }



}

public class SingleLinkedList implements Mylist{
        private ListNode first;//头节点

        private ListNode last;//尾节点

        public void add(Object element){
            if(first==null){//如果头节点为空,将新增节点给头节点
       first=new ListNode(element);
       last=head;//此时尾节点等于头节点
        }else{
        last.next=new ListNode(element);//新增节点
        last=last.Next;//尾节点更新到新增的一个节点位置上
        }

        size++;
}
                  //新增一个元素

    //删除相同元素
  public  void delete(Object element){
        ListNode p=first;
        ListNode pre=null;//p前面的位置
        while(p!=null){
            if(p.data.equals(element)){
                  if(p==first){//如果删除头指针元素，让头指针往后挪一位就可以了
                  first=first.next;
                  }
                pre.next=p.next;
                break;
            }
            pre=p;//等于p的位置，p再移动一位,pre就在p的前面了
            p=p.next;
        }
        size--;
    }
    //根据索引删除元素
   public void delete(int index){
        if(index<0||index>size){
        return;//啥也不干
        }
        int i=0;
        ListNode p=first;
        ListNode pre=null;

        while(p!=null){
          if(i==index){
            if(p==first){
                first=first.next;
            }else{
                pre.next=p.next;

            }
            break;
          }
            pre=p;
            p=p.next;
            i++;
        }

           、size--;
    }

    //将指定索引位置的·元素替换成新元素
    public void update(int index,Object newElement){
        if(index<0||index>=size){
        return;
        }

        int i=0;
        ListNode p=first;

        while(p!=null){
            if(i==index){
            p.data=newElement;
            break;
            }
            p=p.next;
            i++;
        }

    }

    //当前列表中是否含有target元素
   public  boolean contains(Object target){
        ListNode p=first;
        while(p!=null){
            if(p.data.equals(target)){
              return true;
            }
            p=p.next;
        }
        return false;
    }

    //返回指定索引处元素
    public Object at(int index){
    if(index<0||index>size){
        return;//啥也不干
        }
        int i=0;//指针指向的节点的索引
        ListNode p=first;
        while(p!=null){
          if(i==index){
            return p.data;
            break;
          }
            p=p.next;
            i++;
        }
    }


    public int indexOf(Object element){

        int i=0;//指针指向的节点的索引
        ListNode p=first;
        while(p!=null){
          if(p.data.equals(element)){
            return i;
            break;
          }
            p=p.next;
            i++;
        }

    return -1;
    }

        public String toString(){
            StringBuilder sb=new StringBuilder();
            ListNode p=first;
            while(p.next!=null){
            sb.append(p.data).append(",");
            p=p.next;
            }
            sb.append("]");
            return sb.toString();

        }


}

//增和删链表更快

双向链表

first和last是亚元所代表的值为null
          <-    <-    <-
null->head->Node->Node->tail->null
a0     a1    a2    a3
双向链表结构

public class ListNode{
    Object data;
    ListNode pre;
    ListNode next;
    public listNode(Object data){this.data=data;}
}



public class DoubleLinkedList implements Mylist{
        private ListNode first=new ListNode(null);//头节点

        private ListNode last=new ListNode(null);//尾节点

        private size=0;

        public DoubleLinkList(){

        first.next=last;
        last.pre=first;

        }

        public void add(Object element){

        ListNode newNode=new ListNode(element);
        last.pre.next=newNode;
        newNode.next=last;
        newNode.pre=last.pre;
        last.pre=newNode;
        size++;
        }
                  //新增一个元素

    //删除相同元素
   public  void delete(Object element){
        ListNode p=first.next;//first为null
        while(p!=last){
            if(p.data.equals(element)){
                 p.pre.next=p.next;
                 p.next.pre=p.pre;
                 p.next=null;
                 p.pre=null;
                 size--;
                break;
            }
             p=p.next;
        }
    }
    //根据索引删除元素
   public void delete(int index){
        if(index<0||index>size){
        return;//啥也不干
        }
        int i=0;
        ListNode p=first.next;//从first的下一个元素开始

        while(p!=last){
          if(i==index){

          p.pre.next=p.next;
          p.next.pre=p.pre;
          p.next=null;
          p.pre=null;
            size--;
            break;//注意这里
          }
            p=p.next;
            i++;
        }

           、
    }

    //将指定索引位置的·元素替换成新元素
    public void update(int index,Object newElement){
        if(index<0||index>=size){
        return;
        }

        int i=0;
        ListNode p=first.next;

        while(p!=last){
            if(i==index){
            p.data=newElement;
            break;
            }
            p=p.next;
            i++;
        }

    }

    //当前列表中是否含有target元素
   public  boolean contains(Object target){
        ListNode p=first.next;
        while(p!=last){
            if(p.data.equals(target)){
              return true;
            }
            p=p.next;

        }
        return false;

    }

    //返回指定索引处元素
    public Object at(int index){
    if(index<0||index>size){
        return;//啥也不干
        }
        int i=0;//指针指向的节点的索引
        ListNode p=first.next;
        while(p!=last){
          if(i==index){
            return p.data;
            break;
          }
            p=p.next;
            i++;
        }

        return null;
    }


    public int indexOf(Object element){

        int i=0;//指针指向的节点的索引
        ListNode p=first.next;
        while(p!=last){
          if(p.data.equals(element)){
            return i;
            break;
          }
            p=p.next;
            i++;
        }

    return -1;
    }

        public String toString(){
            StringBuilder sb=new StringBuilder();
            ListNode p=first.next;
            while(p!=last){
            sb.append(p.data);
            if(p.next!=last)
            sb.append(",");
            p=p.next;
            }
            sb.append("]");
            return sb.toString();

        }


}

迭代器

public interface Iterator<E>{
    boolean hasNext();

    Object next();

}

public interface MyList extends Iterator{

    //新增一个元素
    void add(Object element);
    //删除相同元素
    void delete(Object element)
    //根据索引删除元素
    void delete(int index);

    //将指定索引位置的·元素替换成新元素
    void update(int index,Object newElement);

    //当前列表中是否含有target元素
    boolean contains(Object target);

    //返回指定索引处元素
    Object indexOf(int index);

      boolean hasNext();

    Object next();

}


public class DoubleLinkedList implements Mylist{
        private ListNode first=new ListNode(null);//头节点

        private ListNode last=new ListNode(null);//尾节点

        private size=0;

        public DoubleLinkList(){

        first.next=last;
        last.pre=first;

        }

        public void add(Object element){

        ListNode newNode=new ListNode(element);
        last.pre.next=newNode;
        newNode.next=last;
        newNode.pre=last.pre;
        last.pre=newNode;
        size++;
        }
                  //新增一个元素

    //删除相同元素
   public  void delete(Object element){
        ListNode p=first.next;//first为null
        while(p!=last){
            if(p.data.equals(element)){
                 p.pre.next=p.next;
                 p.next.pre=p.pre;
                 p.next=null;
                 p.pre=null;
                 size--;
                break;
            }
             p=p.next;
        }
    }
    //根据索引删除元素
   public void delete(int index){
        if(index<0||index>size){
        return;//啥也不干
        }
        int i=0;
        ListNode p=first.next;//从first的下一个元素开始

        while(p!=last){
          if(i==index){

          p.pre.next=p.next;
          p.next.pre=p.pre;
          p.next=null;
          p.pre=null;
            size--;
            break;//注意这里
          }
            p=p.next;
            i++;
        }

           、
    }

    //将指定索引位置的·元素替换成新元素
    public void update(int index,Object newElement){
        if(index<0||index>=size){
        return;
        }

        int i=0;
        ListNode p=first.next;

        while(p!=last){
            if(i==index){
            p.data=newElement;
            break;
            }
            p=p.next;
            i++;
        }

    }

    //当前列表中是否含有target元素
   public  boolean contains(Object target){
        ListNode p=first.next;
        while(p!=last){
            if(p.data.equals(target)){
              return true;
            }
            p=p.next;

        }
        return false;

    }

    //返回指定索引处元素
    public Object at(int index){
    if(index<0||index>size){
        return;//啥也不干
        }
        int i=0;//指针指向的节点的索引
        ListNode p=first.next;
        while(p!=last){
          if(i==index){
            return p.data;
            break;
          }
            p=p.next;
            i++;
        }

        return null;
    }


    public int indexOf(Object element){

        int i=0;//指针指向的节点的索引
        ListNode p=first.next;
        while(p!=last){
          if(p.data.equals(element)){
            return i;
            break;
          }
            p=p.next;
            i++;
        }

    return -1;
    }

        public String toString(){
            StringBuilder sb=new StringBuilder();
            ListNode p=first.next;
            while(p!=last){
            sb.append(p.data);
            if(p.next!=last)
            sb.append(",");
            p=p.next;
            }
            sb.append("]");
            return sb.toString();

        }

        private ListNode now=first;

     public boolean hasNext(){

     return now.next!=last;;
     }

    public Object next(){
    ListNode next=now.next;
    now=now.next;

    return next.data;
    }


}

public iter(){
    while(list.hashNext()){
       String next=list.next();
        System.out.println(next);
    }
}


//<T>泛型可以替换掉object

java List API

 

sort{set,List,Tree}

                     collection
         |               |         |
       List           Set        Queue
   |     |        |
Stack ArrayList LinkedList

List<String> list=new ArrayList<>();
list=new LinkedList<>();
list.add("asda");
list.remove("");

Collection.sort(list);

List<Student>list1=new ArrayList<>();
list1.add(new Student("zhangsan",10));
list1.add(new Student("isli",20));
Collection.sort(list1,(o1,o2)->{//camparetor排序器

    return o1.get()-o2.get();

});


for(int i=0;i<list1.size();i++){
    System.out.println(list1.get(i));
}//不能删东西，需要确保边界

for(Student stu:list1){
    System.out.println(stu);
}


Iterator<Student> iterator=new list1.Iterator();
//Iterator可以
while(iterator.hasNext()){
    System.out,println(iterator.next());
}