符合中小企业对网站设计、功能常规化式的企业展示型网站建设
本套餐主要针对企业品牌型网站、中高端设计、前端互动体验...
商城网站建设因基本功能的需求不同费用上面也有很大的差别...
手机微信网站开发、微信官网、微信商城网站...
动态数组与链表有相同部分,共用一个父类AbstracList,该父类继承接口List
创新互联专注于企业成都全网营销、网站重做改版、潜江网站定制设计、自适应品牌网站建设、HTML5建站、成都做商城网站、集团公司官网建设、成都外贸网站制作、高端网站制作、响应式网页设计等建站业务,价格优惠性价比高,为潜江等各大城市提供网站开发制作服务。数组:查询快,增删慢
链表:查询慢,增删快
2、链表
链表是一种链式存储的线性表,地址不一定是连续的
一个链表包括头结点、普通结点、尾结点
头结点内含:size(链表长度)、first(头指针)
其他结点内含:element(内容)、next(指向下一结点的指针,其中尾结点指针值为null)
头指针供外界使用,其他指针不需要,为静态内部类
private static class Node{
E element; //内容
Nodeprev; //指向前一个结点的指针
Nodenext; //指向下一个结点的指针
public Node(Nodeprev, E element, Nodenext) {
this.prev = prev;
this.element = element;
this.next = next;
}
}
clear()
首先要让size等于0
只需要将头结点的指针指向空即可
其他结点没有头指针连接,会被自动回收,因此不需要管其他的结点
public void clear() {
size = 0;
first = null;
last = null;
}
查找对应位置的结点
通过观察可以发现,从头结点到目标结点使用的指针数目与该结点位置-1相同,因此可以使用for循环,定义一个指针指向头结点地址,不断next直到到达目标结点的地址
private Nodenode(int index){
rangeCheck(index); //查看index是否正常
Nodenode = first;
for(int i = 0; i< index; i++){
node = node.next; //使指针指向下一个结点地址
}
return node;
}
add(int index, E element)
先令要插入的结点指向插入位置原结点
再令前一个结点指向新插入的这个结点
public void add(int index, E element){
if(index == 0){ //由于插入位置为第一个时,node(index - 1)会报错
first = new Node<>(element,first);
}else{
Nodeprev = new node(index - 1); //原位置前一个结点为新结点的前一个结点
prev.next = new Node<>(element,prev.next); //创建新结点并将其与前后结点相连
}
size++;
}
remove(int index)
令删除位置前一个结点的指针指向index+1,删除位置结点被断开后自动垃圾回收
public E remove(int index){ //返回删除位置原来的内容
Nodenode = first;
if(index == 0){
first = first.next;
}else{
Nodeprev = new node(index - 1); //找到前一个结点
node = prev.next; //node就是要删除的结点
prev.next = node.next; //前一个结点连接后一个结点,删除node
}
return node.element;
}
indexOf(E element)
通过循环,找到对应元素的位置
public int indexOf(E element) {
if (element == null) { //空元素单独设条件
Nodenode = first;
for (int i = 0; i< size; i++) {
if (node.element == null) return i;
node = node.next;
}
} else {
Nodenode = first;
for (int i = 0; i< size; i++) {
if (element.equals(node.element)) return i;
node = node.next;
}
}
return -1;
}
虚拟头结点
上述功能基本都会将index=0的情况单独列出来,为了精简这些代码,我们在原头结点前设一个新的头结点,叫虚拟头结点
在头结点前另设一个头结点,它的值为null,它被头指针连接,且next指针指向真正的头结点
//构造函数,内含虚拟头结点的定义
public linklist(){
first = new Node<>(null,null);
}
双向链表
拥有两个指针:头指针first和尾指针last,分别连接链表的头部和尾部,从而让链表连成一个环
每个结点又各自拥有两个指针,一个是与单向链表相同的next指针,从头指向尾的方向;另一个是prev指针,与next方向相反,从尾指向头
因此要找某个结点,比较它的index与1/2size的大小,小于说明离头结点比较近,用next指针,大于说明离尾结点比较近,用prev指针
双向链表添加元素,不需要寻找元素前一个结点(已经有prev指针了)
index不是0也不等于size时,顺序:添加结点的next连接原为index处的结点,prev连接这个结点的前一个结点,即index-1位置的结点;后一个结点的prev连接添加结点,前一个结点的next连接添加结点
Nodenext = node(index); //新结点的next为相应index位置的结点
Nodeprev = next.prev; //新结点的prev连接index位置结点的前一个结点
Nodenode = new Node<>(prev,element,next); //创建新结点
next.prev = node; //新结点变成获取结点的前一个结点,即变成了index位置的结点
prev.next = node; //新结点再与前一个结点的next相连
index为0时:头指针first改变,需要与添加结点相连,添加结点的prev变为null,也是上述代码中的prev = next.prev,唯一需要改动的就是prev是null时它没有next,所以最后一句代码进行修改:
if(next == first){
first = node; //新结点就是头结点,与头指针相连
}else{
prev.next = node;
}
index为size时,尾指针last改变,需要与添加结点相连,添加结点的next变成null,原先的尾结点的next指向它
如果链表是空的,添加元素是链表第一个结点,last.prev不存在
if(index == size){
Nodeoldlast = last; //旧的尾结点
last = new Node<>(oldlast,element,null); //新的尾结点,它的prev指向oldlast,next指向null
if(oldlast == null){ //如果这是第一个结点
first = last; //头指针尾指针都指向新结点
}else{
oldlast.next = last;
}
}
删除某个结点时,由于双向链表能够轻松找到结点的前一个结点与后一个结点,所以只需要让他们断开(前一结点的next指向后一结点,后一结点的prev指向前一结点),再把index为0和size单独处理即可
单向循环链表:与单向链表不同的是,它的尾结点的next指向头结点
双向循环链表:比单向循环链表多一个,头结点的prev指向尾结点
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧