网创优客建站品牌官网
为成都网站建设公司企业提供高品质网站建设
热线:028-86922220
成都专业网站建设公司

定制建站费用3500元

符合中小企业对网站设计、功能常规化式的企业展示型网站建设

成都品牌网站建设

品牌网站建设费用6000元

本套餐主要针对企业品牌型网站、中高端设计、前端互动体验...

成都商城网站建设

商城网站建设费用8000元

商城网站建设因基本功能的需求不同费用上面也有很大的差别...

成都微信网站建设

手机微信网站建站3000元

手机微信网站开发、微信官网、微信商城网站...

建站知识

当前位置:首页 > 建站知识

java链表-创新互联

动态数组与链表有相同部分,共用一个父类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元起,快前往官网查看详情吧


网站名称:java链表-创新互联
分享路径:http://bjjierui.cn/article/doshhe.html

其他资讯