链表总结
链表小结
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的，、。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一处结点地址的指针域。相比于线性表顺序结构，链表的一个重要特点是插入、删除操作灵活方便，不需移动结点，只需改变结点中指针域的值即可。链表分为以下三种：
1、单向链表的每一个结点由存储数据元素的数据域和指向下一个结点的指针域组成。
2、双向链表其实是单链表的改进。结点除含有数据域外，还有两个链域，一个存储直接子结点地址，一般称之为右链域；一个存储直接父结点地址，一般称之为左链域。这样的结构不仅可以进行从前往后的查询等操作，也可以从某结点开始往前进行查询等操作。着重讲解双向链表中的自定义队列：最基本的使用就是能够实现数据的查找、插入、删除、合并、统计以及简单计算等的操作。
首先需要定义一个结点类
/**
* 链表结点类
* @author Administrator
*
*/
public class LinkNode {
private Object obj;//定义数据对象
private LinkNode child;//下一个结点的引用
private LinkNode parent;//上一个结点的引用
//在创建节点对象的时候就传入节点中的数据对象
public LinkNode(Object obj) {
this.obj=obj;
}
public Object getObj() {
return obj;
}
public void setObj(Object obj) {
this.obj = obj;
}
public LinkNode getChild() {
return child;
}
public void setChild(LinkNode child) {
this.child = child;
}
public LinkNode getParent() {
return parent;
}
public void setParent(LinkNode parent) {
this.parent = parent;
}
}
/**
* 双向链表类
* @author Administrator
*
*/
public class LinkList {
public static LinkNode root =null;//第一个结点
public LinkNode last =root;//最后一个结点
private Object obj;//定义数据对象
//函数入口
public static void main(String[] args) {
LinkList list =new LinkList();
//加入结点
list.add("新增加的结点一");
list.add("新增加的结点二");
list.add("新增加的结点三");
list.add("新增加的结点四");
//得到链表的长度
list.size();
//插入结点
list.insertIndexObj(1, "aaa")；
//遍历链表
list.printLinKList(root);
}
//得到链表长度的方法
public int size(){
int count=1;//定义计数变量
if(null == root){//如果链表为空
return 0;
}
//链表不为空，得到根结点后的下一个结点
LinkNode node =root.getChild();
while(null !=node){//若链表不为空
count++;
node=node.getChild();//得到下一个结点
}
//输出结点数
System.out.println("结点数为："+count);
return count;
}
//在指定索引下插入结点
public void insertIndexObj(int index,Object obj){
//若索引值不在链表长度范围内，则越界
if(this.size()<index || index <0){
throw new java.lang.RuntimeException("下标越界："+index+",size:"+this.size());
}else{
//创建一个新的结点
LinkNode newNode=new LinkNode(obj);
//得到当前索引位置的结点
LinkNode node=this.getLinkNode(index);
if(index==0){//链表没结点
root=newNode;//插入的结点为头结点
System.out.println(">>>>>>>>>>>>>>>>>");
} else{
//得到父结点
LinkNode fNode =node.getParent();
//设置新的引用关系
fNode.setChild(newNode);
newNode.setParent(fNode);
}
//设置新的引用关系
newNode.setChild(node);
node.setParent(newNode);
}
}
//插入结点
public void add(Object obj){
//创建新结点
LinkNode node =new LinkNode(obj)；
if(null==root){//链表为空
root =node;//插入的结点为根结点
last=root;
}else {
last.setChild(node);
node.setParent(last);
last=node;
}
}
//遍历
public void printLinKList(LinkNode root){
if(null !=root){
//得到结点数据
Object data=root.getObj();
//输出结点数据
System.out.println(data);
//得到下一个结点
LinkNode temp=root.getChild();
//递归
printLinKList(temp);
}
}
}
链表中删除、修改等操作与上述的插入结点操作类似，因此在这就不一一写出了。
3、循环链表是单向链表的延伸，只要将最后一个结点的指针指向该循环链表的根结点或第一个结点，形成了环形链表。
由于链表的插入、删除操作灵活方便，我们可以在程序运行期间根据需 要动态申请内存，为新结点分配存储空间，并通过修改指针将新结点链接到链表上。因此，链表是一种动态数据结构。
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的，、。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一处结点地址的指针域。相比于线性表顺序结构，链表的一个重要特点是插入、删除操作灵活方便，不需移动结点，只需改变结点中指针域的值即可。链表分为以下三种：
1、单向链表的每一个结点由存储数据元素的数据域和指向下一个结点的指针域组成。
2、双向链表其实是单链表的改进。结点除含有数据域外，还有两个链域，一个存储直接子结点地址，一般称之为右链域；一个存储直接父结点地址，一般称之为左链域。这样的结构不仅可以进行从前往后的查询等操作，也可以从某结点开始往前进行查询等操作。着重讲解双向链表中的自定义队列：最基本的使用就是能够实现数据的查找、插入、删除、合并、统计以及简单计算等的操作。
首先需要定义一个结点类
/**
* 链表结点类
* @author Administrator
*
*/
public class LinkNode {
private Object obj;//定义数据对象
private LinkNode child;//下一个结点的引用
private LinkNode parent;//上一个结点的引用
//在创建节点对象的时候就传入节点中的数据对象
public LinkNode(Object obj) {
this.obj=obj;
}
public Object getObj() {
return obj;
}
public void setObj(Object obj) {
this.obj = obj;
}
public LinkNode getChild() {
return child;
}
public void setChild(LinkNode child) {
this.child = child;
}
public LinkNode getParent() {
return parent;
}
public void setParent(LinkNode parent) {
this.parent = parent;
}
}
/**
* 双向链表类
* @author Administrator
*
*/
public class LinkList {
public static LinkNode root =null;//第一个结点
public LinkNode last =root;//最后一个结点
private Object obj;//定义数据对象
//函数入口
public static void main(String[] args) {
LinkList list =new LinkList();
//加入结点
list.add("新增加的结点一");
list.add("新增加的结点二");
list.add("新增加的结点三");
list.add("新增加的结点四");
//得到链表的长度
list.size();
//插入结点
list.insertIndexObj(1, "aaa")；
//遍历链表
list.printLinKList(root);
}
//得到链表长度的方法
public int size(){
int count=1;//定义计数变量
if(null == root){//如果链表为空
return 0;
}
//链表不为空，得到根结点后的下一个结点
LinkNode node =root.getChild();
while(null !=node){//若链表不为空
count++;
node=node.getChild();//得到下一个结点
}
//输出结点数
System.out.println("结点数为："+count);
return count;
}
//在指定索引下插入结点
public void insertIndexObj(int index,Object obj){
//若索引值不在链表长度范围内，则越界
if(this.size()<index || index <0){
throw new java.lang.RuntimeException("下标越界："+index+",size:"+this.size());
}else{
//创建一个新的结点
LinkNode newNode=new LinkNode(obj);
//得到当前索引位置的结点
LinkNode node=this.getLinkNode(index);
if(index==0){//链表没结点
root=newNode;//插入的结点为头结点
System.out.println(">>>>>>>>>>>>>>>>>");
} else{
//得到父结点
LinkNode fNode =node.getParent();
//设置新的引用关系
fNode.setChild(newNode);
newNode.setParent(fNode);
}
//设置新的引用关系
newNode.setChild(node);
node.setParent(newNode);
}
}
//插入结点
public void add(Object obj){
//创建新结点
LinkNode node =new LinkNode(obj)；
if(null==root){//链表为空
root =node;//插入的结点为根结点
last=root;
}else {
last.setChild(node);
node.setParent(last);
last=node;
}
}
//遍历
public void printLinKList(LinkNode root){
if(null !=root){
//得到结点数据
Object data=root.getObj();
//输出结点数据
System.out.println(data);
//得到下一个结点
LinkNode temp=root.getChild();
//递归
printLinKList(temp);
}
}
}
链表中删除、修改等操作与上述的插入结点操作类似，因此在这就不一一写出了。
3、循环链表是单向链表的延伸，只要将最后一个结点的指针指向该循环链表的根结点或第一个结点，形成了环形链表。
由于链表的插入、删除操作灵活方便，我们可以在程序运行期间根据需 要动态申请内存，为新结点分配存储空间，并通过修改指针将新结点链接到链表上。因此，链表是一种动态数据结构。