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

本文主要是介绍数据结构(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;}
4public  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的索引，如果没有返回-1Object 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为nullwhile(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为nullwhile(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 LinkedListList<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());
}

这篇关于数据结构(data structure)（1）链表和线性表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---