首页 / JAVA / 双链表实现——Java
双链表实现——Java
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了双链表实现——Java，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4383字，纯文字阅读大概需要7分钟。
内容图文
链表的产生：保存多个对象，对象数组，但数组一旦定义长度固定---->链表
链表：插入删除：O(1) 随机访问：O(n)
数组：插入删除：O(n) 随机访问：O(1)
双向链表：
Node类：负责结点内容的设置，真实保存内容
link类：负责结点（处理Node类之间的关系）之间的动态挂载，用户使用的是link类
用户只需要通过Link类的add方法设置数据。link.add("数据")，对用户屏蔽了挂载操作
interface Ilink{
/**
* 链表的增加结点操作
* @param data 节点内容
* @return
*/
boolean add(Object data);
/**
* 删除指定内容结点
* @param data 结点内容
* @return 返回删除的节点内容
*/
Object remove(Object data);
/**
* 根据下标删除结点
* @param index 指定的下标
* @return
*/
Object remove(int index);
/**
* 根据指定下标返回结点内容
* @param index 指定下标
* @return
*/
/**
* 清空链表
*/
void removeAll();
Object get(int index);
/**
* 根据结点内容判断指定的结点是否存在
* @param data 结点内容
* @return 返回结点内容所在的下标
*/
int contains(Object data);
/**
* 根据指定下标修改结点内容
* @param data 要修改的内容
* @return 返回替换之前的结点
*/
Object set(Object data,int index);
/**
* 将链表转为数组
* @return 返回数组
*/
Object[] toArray();
/**
* 取得链表长度
* @return
*/
int size();
/**
* 打印链表
*/
void printLink();
}
class Link implements Ilink{
private Node head;
private Node last;
private int size;
private class Node{
private Object data;
private Node prev;
private Node next;
public Node(Object data, Node prev, Node next) {
this.data = data;
this.prev = prev;
this.next = next;
}
}
public Node getHead() {
return head;
}
public Node getLast() {
return last;
}
@Override
public boolean add(Object data) {
Node node = new Node(data,this.last,null);
if(this.last!=null){
this.last.next = node;
}
this.last = node;
size++;
if(this.head==null){
this.head = node;
}
return true;
}
@Override
public Object remove(Object data) {
Object old = null;
if(data==null){
for(Node node = head;node!=null;node=node.next) {
if(node.data==null){
old = node.data;
del(node);
}
}
return old;
}else{
for(Node node = head;node!=null;node=node.next) {
if(node.data==data){
old = node.data;
del(node);
}
}
return old;
}
}
private void del(Node node){
if(node == null){
return;
}
if(node==this.head){
this.head = node.next;
}else{
node.prev.next = node.next;
}
if(node==this.last){
this.last = node.prev;
}else{
node.next.prev = node.prev;
}
node.data = node.prev = node.next = null;
node = null;
size--;
}
@Override
public Object remove(int index) {
if(isIndex(index)){
int i = 0;
Object old = null;
for(Node node = head;node!=null;node=node.next) {
if(i==index){
old = node.data;
del(node);
}
i++;
}
return old;
}
return null;
}
@Override
public void removeAll() {
if(this.size==0){
return ;
}
for(Node node = head;node!=null;) {
Node temp = node.next;
node.data = node.prev = node.next = null;
node = null;
node = temp;
size--;
}
this.head = null;
this.last = null;
}
public boolean isIndex(int index){
return (index>=0&&index<this.size);
}
@Override
public Object get(int index) {
if(isIndex(index)){
int i = 0;
for(Node node = head;node!=null;node=node.next) {
if(i==index){
return node.data;
}
i++;
}
}
return null;
}
@Override
public int contains(Object data) {
int i = 0;
if(data==null){
for(Node node = head;node!=null;node=node.next) {
if(node.data==null){
return i;
}
i++;
}
}else{
for(Node node = head;node!=null;node=node.next) {
if(node.data==data){
return i;
}
i++;
}
}
return -1;
}
@Override
public Object set(Object data,int index) {
if(isIndex(index)){
int i = 0;
Object oldData = null;
for(Node node = head;node!=null;node=node.next){
if(i==index){
oldData = node.data;
node.data = data;
}
i++;
}
return oldData;
}
return null;
}
@Override
public Object[] toArray() {
Object[] arr = new Object[this.size];
int i = 0;
for(Node node = head;node!=null;node=node.next){
arr[i] = node.data;
i++;
}
return arr;
}
@Override
public int size() {
return this.size;
}
@Override
public void printLink() {
for(Node node = head;node!=null;node=node.next){
System.out.print(node.data+"——>");
}
System.out.println();
}
}
public class Test {
public static void main(String[] args) {
Ilink link = new Link();
link.add("火车头");
link.remove(0);
link.add("车厢1");
link.add("车厢2");
link.add("车厢3");
link.add("车厢4");
link.add("车厢5");
link.add("车厢6");
link.add("车厢尾");
link.printLink();
System.out.println(link.remove(0));
System.out.println(link.remove("车厢尾"));
System.out.println(link.set("hah",3));
System.out.println(link.contains("hah"));
System.out.println(link.toArray());
link.printLink();
System.out.println(((Link) link).getHead());
System.out.println(((Link) link).getLast());
link.removeAll();
System.out.println(link.size());
}
}
内容总结
以上是互联网集市为您收集整理的双链表实现——Java全部内容，希望文章能够帮你解决双链表实现——Java所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】