链表 小结

                                链表 小结

一 .介绍

链表与集合框架里的队列以及数组不同,它是一种非连续 ,非顺序的存储结构,而且其储存的数据元素是通过链表中的引用链接次序实现的.链表是由一系列结点组成的,结点的生成与队列相同,可以在运行时动态生成.

每个结点包括两个部分:一个是储存数据元素的数据域;另一部分则是用来储存下一个结点地址的指针域.正因为如此,链表在数据元素的插入和删除方面相当有优势.

二.分类及使用

链表主要分为三类:单链表,双链表,和环链表,每种适用于不同的情况.

三者的操作方式相同,主要包括:链表的创建,指定元素的添加,修改,删除,以及查找,以上的操作可以通过具体指定元素对象或者是对应的索引进行,大致上看链表的操作与集合框架的极为相似.

下面通过对双链的操作介绍几种基本的操作方式:

1.指定元素的添加: 

 

  

public void add(int index, Object object) {
		 // 创建对应元素的结点
		LinkNode temp = new LinkNode(object);
		// 判断是否索引越界
		if (index > getSize() || index < 0) {
			// 抛出运行时错误
			throw new RuntimeException("索引越界" + "size:" + getSize()
					+ "; index:" + index);

		} else if (head == null) {

			head = temp;
			foot = head;

		} else if (index == getSize()) {
			// 如果所需添加的对象到链表最后
			foot.setChildren(temp);
			temp.setParent(foot);
			foot = temp;

		} else if (index == 0) {
// 如果所需添加的对象到链表最前
			temp.setChildren(temp);
			head.setParent(temp);
			head = temp;

		} else {
			// 获取插入位置的父节点和字节点
			LinkNode node = get(index);
			LinkNode fnode = node.getParent();
			// 重新设定关系
			temp.setParent(fnode);
			fnode.setChildren(temp);

			temp.setChildren(node);
			node.setParent(temp);
		}

	}

 

 

2. 打印链表中所有元素

 

 

public void printLinkList() {

		// 递归算法
		// if (root != null) { Object date = root.getObj();
		// System.out.println(date); LinkNode temp = root.getNext();
		// printLinkList(temp); }

		// 循环输出
		LinkNode node = head;
		while (node != null) {
			System.out.println(node.getObj());
			node = node.getChildren();

		}
	}

  

 

 

    3.获得 指定元素在链表中的索引

     

public int contain(LinkNode node) {
		int index = 0;
		LinkNode temp = head;// 获得链表头
		while (temp != null) {// 判断是否为空
			if (temp.getObj().equals(node.getObj())) {// 判断是否相等
				return index;// 返回索引
			} else {
				index++;
				temp = temp.getChildren();
			}
		}
		return -1;// 没找到则返回-1
	}