数据结构之链表

 

数据结构之链表

 

 

链表的基本概念

 

链表是一种物理上不连续，逻辑上上连续的存储结构。其逻辑上连续的特性是由链表中的指针指向实现的。

链表是由一系列节点构成的，每个节点都由两个部分组成：一是存储数据元素的数据域，二是存储相关联节点地址的指针域。

根据指针域的不同，可将链表分为：单向链表，双向链表，循环链表。

 

一．单向链表

 

单向链表是指，指针域中的指引只有一个，即指向下一个节点的地址。

 

 

二．双向链表

 

双向链表含有2个指针域，分别指向上一个和下一个节点的地址。相比较单向链表，双向链表的优越性体现在，查找某个元素的时候，单向链表必须从头结点开始，而双向链表则可以避免这种弊端。

一般，我们把双向链表，存储直接子节点的链域称为右链域，存储直接父节点的链域称为左链域。

 

以下以双向链表的增删改查基本操作介绍：

 

1）链表的创建最基本的是节点的建立

 

public class LinkNode {
          private Stuff obj;// 结点内的数据对象,即员工类
          private LinkNode last;// 上一个结点的引用
          private LinkNode next;// 下一个结点的引用
          public LinkNode( Stuff obj) {//构造函数
               this.obj=obj;
              }
         public Stuff getObject() {//得到数据
              return obj;
             }
          public void setObject(Stuff obj) {//设置数据域
              this.obj = obj;
             }
           public LinkNode getLast() {//得到上一个节点
               return last;
                  }
           public void setLast(LinkNode last) {//设置上个节点
                 this.last = last;
              }

             public LinkNode getNext() {//得到下个节点
              return next;
                  }
             public void setNext(LinkNode next) {//设置下个节点
                       this.next = next;
                     }
}

 

 

2）插入节点

 

  A）顺序插入

 

        public void add(LinkNode node) {

                          if (null == root) {// 链表是空。Root:根节点
                                  root = node;
                                  end = root;
                              } else {
                                      end.setNext(node);//设置关系
                                      node.setLast(end);
                                     end = node;
                                      }
 }

 

 

 B）在指定索引出插入节点

 

public void insertIndex(int index, Stuff obj) {
		if (this.getLength() < index || index < 0) {
			throw new RuntimeException("下标越界:" + index + ",size:"
					+ this.getLength());
		} else {
			// 创建一个新的节点
			LinkNode newnode = new LinkNode(obj);
			// 得到当前索引位置的节点
			LinkNode node = this.getLinkNode(index);
			if (index == 0) {// 如果链表没有节点
				root = newnode;

			} else {
				// 得到上一个节点,此时都是从指引前插入
				LinkNode Lnode = node.getLast();
				Lnode.setNext(newnode);
				newnode.setLast(Lnode);
			}
			newnode.setNext(node);
			node.setLast(newnode);
		}

	}

 

 

 

 

2）删除节点

 

public void deleteLinkList(int index, Object obj) {
                     if (this.getLength() < index || index < 0) {
                             throw new RuntimeException("下标越界:" + index +                               ",size:"+ this.getLength());
                     } else {
                              // 得到当前索引位置的节点
                                LinkNode node = this.getLinkNode(index);
                              // 得到上一个节点
                                  LinkNode Lnode = node.getLast();
                                  LinkNode Nnode = node.getNext();
                                      if (Lnode == null) {
                                                       root = Nnode;
                                              } else if (Nnode == null) {
                                                         Lnode.setNext(null);
                                                           } else {
                                                       Lnode.setNext(Nnode);//直接设置上一个节点域下一个节点的关  联关系，要删除的节点自动被删除
                                                          Nnode.setLast(Lnode);
                                         }
                                      }
}

 

 

3）查找节点

public LinkNode getLinkNode(int index) {
		if (this.getLength() < index || index < 0) {
			throw new RuntimeException("下标越界:" + index + ",size:"
					+ this.getLength());
		} else {
			int count = 0;
			LinkNode node = root;
			;
			while (count != index) {
				node = node.getNext();
				count++;
			}
			return node;
		}
	}

 

 

 

4）得到链表长度

public int getLength() {
		int count = 0;
		if (root == null) {
			return count;
		}
		LinkNode node = root.getNext();
		while (node != null) {
			count++;
			node = node.getNext();
		}
		return count + 1;
	}

 

 

5）改变节点对象

public void UpdateLinkNode(int index, Stuff obj) {
		if (this.getLength() < index || index < 0) {
			throw new RuntimeException("下标越界:" + index + ",size:"
					+ this.getLength());
		} else {
			// 得到当前索引位置的节点
			LinkNode node = this.getLinkNode(index);
			node.setObject(obj);
		}
	}

 

 

6）遍历链表

public  void printLinkList(LinkNode root) {
		if (null != root) {//如果根节点不为空
			Stuff p=(Stuff) root.getObject();//得到数据域对象
			LinkNode temp=root.getNext();//得到下一个节点
			printLinkList(temp);//递归调用

			
		}

	}