数据结构(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());
}
原文地址：https://blog.csdn.net/valutang/article/details/137516739
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！