1.什么是链表
链表是一种物理储存单元上非连续,非顺序的储存结构,链表由一系列节点组成,节点可以在运行
时动态生成。每个节点包括两个部分:一个是储存元素数据的数据域,另一个是储存下一个节点地址的指针域。
2.链表的构建
下面以一个双向链表为例构建链表
首先定义一个链表接口,代码如下:
public interface NodeLinkedListInterface {
/**
* 添加节点的方法
*
* @param node新添加的节点对象
*/
public abstract void add(Node node);
/**
* 在指定索引位置添加新节点
*
* @param node要添加的新节点
* @param index指定的索引位置
*/
public abstract void add(Node node, int index);
/**
* 让指定位置的节点互相交换位置
* @param index1,index2指定的节点位置
*/
public abstract void exchange(int index1,int index2);
/**
* 移除指定的节点
*
* @param node要被移除的节点对象
* @return 返回true和false,true表示移除成功,false表示移除失败
*/
public abstract boolean remove(Node node);
/**
* 移除指定所以位置的节点
*
* @param index指定要移除的节点索引
* @return 返回true和false,true表示移除成功,false表示移除失败
*/
public abstract boolean remove(int index);
/**
* 获取指定索引位置的节点对象
*
* @param index指定的索引位置
* @return 返回节点对象,如果index的范围超出size,则返回null.
*/
public abstract Node get(int index);
/**
* 获取双链表中存储的元素总数
*
* @return 返回size的值,如果为0则表示链表中没有节点
*/
public abstract int size();
}
定义节点类:
public class Node {
private Object obj;
private Node next;
private Node previous;
public Node(Object obj){
this.obj=obj;
}
public Node(Object obj, Node next, Node previous) {
super();
this.obj = obj;
this.next = next;
this.previous = previous;
}
public Object getObj() {
return obj;
}
public void setObj(Object obj) {
this.obj = obj;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public Node getPrevious() {
return previous;
}
public void setPrevious(Node previous) {
this.previous = previous;
}
}
然后实现接口,代码如下:
public class LinkedList implements NodeLinkedListInterface {
private int size;
private Node root = null;
private Node last = null;
public LinkedList() {
this.size = 0;
}
/**
* 链表构造方法
*
* @param size
* @param root
* @param last
*/
public LinkedList(int size, Node root, Node last) {
super();
this.size = size;
this.root = root;
this.last = last;
}
public void add(Node node) {
size++;
if (root == null) {
root = node;
root.setPrevious(null);
last = root;
} else {
last.setNext(node);
node.setPrevious(last);
node.setNext(null);
last = node;
}
public void add(Node node, int index) {
if (index < 0 || index > size) {
System.out.println("没有该位置");
} else if (index == 0) {
Node cnode = root;
root = node;
node.setNext(cnode);
cnode.setPrevious(node);
} else {
Node newnode = this.get(index);
// 获取父节点
Node fnode = newnode.getPrevious();
// 使父节点指向要添加的节点
fnode.setNext(node);
node.setPrevious(fnode);
node.setNext(newnode);
newnode.setPrevious(node);
}
size++;
}
public boolean remove(Node node) {
Node newnode = root;
for (int i = 0; i < size; i++) {
if (newnode == node) {
// 获取要移除的节点的父节点和子节点,使其相连
Node fnode = newnode.getPrevious();
Node cnode = newnode.getNext();
if (fnode == root) {
root = root.getNext();
} else if (cnode == last) {
last = last.getPrevious();
} else {
fnode.setNext(cnode);
cnode.setPrevious(fnode);
newnode = null;
}
break;
} else {
newnode = newnode.getNext();
}
}
size--;
return false;
}
public boolean remove(int index) {
if (index < 0 || index > size) {
System.out.println("没有该位置");
} else {
Node node = this.get(index);
// 获取要移除的节点的父节点和子节点,使其相连
Node fnode = node.getPrevious();
Node cnode = node.getNext();
if (fnode == null) {
root = root.getNext();
} else if (cnode == null) {
last = last.getPrevious();
} else {
fnode.setNext(cnode);
cnode.setPrevious(fnode);
node = null;
}
}
size--;
return false;
}
public Node get(int index) {
if (index < 0 || index > size) {
System.out.println("要返回的结果不存在");
return null;
}
Node node = root;
for (int i = 0; i < index; i++) {
node = node.getNext();
}
return node;
}
public int size() {
return size;
}
}
3.链表的优缺点
优点:1.方便添加和删除
2.长度可以变
缺点:1.访问效率低
分享到:
相关推荐
数组和链表总结 数组和链表.txt
链表是学习数据结构的大门,在微软等大公司招聘c\c++技术人员的时候有3个会必然出现 的东西,指针、链表、二叉树!
c语言中链表的学习,总结相当到位,对于初学者有很大的帮助!
链表总结,c语言版本,巩固基础知识,适用于求职面试,来自互联网,版权归著者
链表是最基本的数据结构,凡是学计算机的必须的掌握的,在面试的时候经常被问到,关于链表的实现,百度一下就知道了。 在此总结一下与链表相关的练习题。题目很全,好好消化。
java 链表心得,对于感到困难的朋友会有很大帮助,与其他语言互通
做有关链表的编程时,这个很实用! 不信试试! 我个人是觉得在做有关链表的程序时,是很好用的
数据结构,链表所有综合面试题型汇总,有大神漏缺的给我留言
C语言中关于链表的总结内容,内附代码例题,详细的有条理的讲解链表内容
php数组当链表-php数组和链表的区别总结 数组和链表.pdf
面试题总结:数组和链表的区别 数组和链表.pdf
城市链表课程设计里面含有详细文档,以及实现代码,资源完整。
多种方法实现链表的逆置。 c语言编写,可以任意字符输入。
1. 剑指offer 22.返回倒数第k个节点:林伟龙 【20:15-20:34】法思路1. 遍历第次链表计算链表度2. 遍历第次链表找到 第 k 个 元素法
php数组和链表的区别总结 数组和链表.pdf
数组和链表的对比分析 数组和链表.docx
顺序存储和链式存储 1 数组—顺序存储 1 链表—链式存储 2 链表概述 3 单链表 4 单链表概念和简单的设计 4 链表的初始化 5 头插入法创建单链表 6 尾插入法创建单链表 7 遍历单链表如打印、修改 8 ...关于链表的总结 23
数据结构的实验报告2链表的基本操作运算 实验内容 编写程序实现链表的建立和基本运算,并完成以下功能: 1、初始化链表、建立新链表。 2、查找节点。 3、 删除节点。 4、 插入节点。 5、 获得链表长度。 6、 退出。
动态链表,处理动态链表的函数,对动态链表的操作,对链表的插入操作(insert)等等
数组和链表的区别和优缺点总结 数组和链表.pdf