数据结构之链表

数据在计算机内有两种存储结构，一种是顺序结构，另一种是树形（索引）结构。在顺序结构里面一般分为数组和链表两种结构。数组是一种物理地址上连续，即在内存中为连续的一个块。而链表是一种逻辑上的连续，数组可以通过下标来查找到数组中的一个值。而链表是通过一个根节点开始遍历来查找值。
数组与链表各有优缺点。数组方便查找。链表方便插入与删除等修改操作。

数组的结构大家应该都有所了解。这里讲一讲链表的数据结构，它是一种链式的，形象的说就是一环紧扣一环的形状。有一种顺藤摸瓜的意思，每一个链表中的节点都连着它的上一节点与下一节点，要想找到一个目标节点就要知道它的上一个节点是谁。那么所有节点的根源就是那个根节点。每个节点都有一个数据域与child域（标准化的说法），数据域就是此节点内保存的data，而child域里面存的就是它的下一个节点，它指向了它下一个是谁。
所以我们如果要进行增删改查的操作就很方便了，如果要删除某个节点，只需将此节点的child域指向null，并且将此节点的上一个节点指向本来此节点的下一个节点。这样它就退出了这个链表。插入操作也是同样的原理。只需修改child域，当然，如果要更加方便的话我们可以在节点中再增加一个parent域，这样就是双向链表了。不仅可以正着遍历，也可以倒着遍历。
下面给出链表的源代码：
首先定义节点及其成员变量
package LinkListTest;

/**
* 链表节点
*
* @author bug
*
*/
public class linkNode {
// 节点内的数据对象
private Object obj;
//对下一个节点的引用
private linkNode next;
/**
* 带节点数据的构造方法
* @param obj
*/
public linkNode(Object obj){
this.obj=obj;
}
public linkNode(){

}
/**
* 返回节点内数据
* @return
*/
public Object getObj(){
return obj;
}
/**
* 设置节点数据
* @param obj
*/
public void setObj(Object obj){
this.obj=obj;
}
/**
  * 设置当前结点的下一个节点
  * @param next
  */
public void setNext(linkNode next){
this.next=next;
}
/**
  * 得到下一节点
  * @return
  */
public linkNode getNext(){
return next;
}
}










然后进行链表的创建并运行：

package LinkListTest;

/**
* 链表
*
* @author bug
*
*/
public class linkList {
public static int count = 0;
public static linkNode root = null;
public static linkNode tail = null;

public static void main(String[] args) {
linkList list = new linkList();
for (int i = 1; i < 4; i++) {
list.addNode(i);
}
//打印链表
list.printList(root);
//得到第2个元素
linkNode n = list.getNode(2);
System.out.println("得到的元素是"+n.getObj());
//在2号位插入元素
list.insertNode(1, "插入元素i");
//打印链表
list.printList(root);
}

/**
* 创建链表
*
* @return
*/
public void addNode(Object data) {
//实例化一个节点
linkNode node = new linkNode(data);
//如果插入节点时链表为空。姐将插入的节点设为根节点,尾节点的指针下一个节点设置为空
if (root == null) {
root = node;
tail = root;
tail.setNext(null);
}
//否则将新节点插入链表尾，更新尾节点
else {
tail.setNext(node);
tail = node;
tail.setNext(null);
}
count++;
}

public void insertNode(int index, Object data) {
//如果待插入下标非法，退出
if (this.size() < index || index < 0) {
System.out.println("下标值非法");
return;
}
//正确下标时，实例化一个待插入节点，实例化一个遍历链表的节点
linkNode newNode = new linkNode(data);
linkNode pNode = new linkNode();
//将遍历节点初始化为根节点
pNode = root;
//当不是把插入节点作为根节点时，就是不在第一个位置插入元素时
if(this.getNode(index)!=root){
//循环pNode为下标index的上一个节点
while(pNode.getNext()!=this.getNode(index)){
pNode=pNode.getNext();
}
//将新节点插到pNode后面
        newNode.setNext(pNode.getNext());
        pNode.setNext(newNode);
        }
//当是把插入节点作为根节点时，将新节点插入链表头
else{
newNode.setNext(root);
root=newNode;
}
}
   

/**
* 得到第index个节点
*
* @param index节点数
* @return返回节点
*/
public linkNode getNode(int index) {
linkNode node = new linkNode();
if (index > this.size()) {
Exception e = new Exception();
System.out.println("下标非法");
}
node = root;
index--;
while (index > 0) {
node = node.getNext();
index--;
}
return node;
}

/**
* 打印链表
*
* @param root
*/
public void printList(linkNode root) {
if (root != null) {
// 得到根节点数据
Object data = root.getObj();
// 输出根节点数据
System.out.println(data);
// 根节点指向下一个节点
linkNode temp = root.getNext();
// 递归
printList(temp);
}

}

public int size() {
return count;
}
}