数据结构之链表

链表是一组地址不连续的顺序存储空间，而数组是地址连续的存储空间。

链表的组成结构：链表是由一系列节点组成，节点可以动态生成。每个节点都由数据域和指针域组成。数据域就是此节点代表的值，指针域就是下一个节点的地址。

链表分为单链表、双链表、循环链表。

在编程过程中经常用到的是双向链表。双向链表有两个指针域，一个指针指向它的后继结点，一个指针指向它的前驱结点。头结点的前驱为空（null)，最后一个节点的后继为空。

下面的java代码部分实现的是双向链表的增删改查功能。

双向链表添加字符串方法， 自动在最后一个节点的后面添加元素。

public void add(String s) {
		Node n = new Node(s);
		if (head == null) {
			head = n;
			foot = head;
		} else {
			// feet=foot;
			foot.next = n;
			n.front = foot;
			foot = n;
			// foot.front=feet;
		}
		count++;
	}

count是记录双向链表的长度size；

 

在链表中插入元素(根据下标位置插入相应的字符串)

/**
	 * 插入元素
	 * 
	 * @param index	插入的下标位置
	 * @param s	插入的名字
	 *       
	 */
	public void add(int index, String s) {
		// 要插入的結點
		Node node = new Node(s);
		if (index == 0) {
			node.next = head;
			head.front = node;
			head = node;
		} else if (index < size()) {
			// 得到下标节点
			Node n = getIndex(index);
			n.front.next = node;
			node.front = n.front;
			node.next = n;
			n.front = node;
		} else if (index == size()) {
			foot.next = node;
			foot = node;
		}
		count++;
	}

 删除链表元素：一种是根据下标删除元素，另外一种是根据内容删除元素。

public void remove(int index) {
		// Node n=getIndex(index);
		// n.next.front=n.front;
		// n.front.next=n.next;

		if (index < 0 || index >= size()) {
			throw new IndexOutOfBoundsException("下标位置超界，index：" + index
					+ ",size：" + size());
		}
		if (index == 0) {
			// 完全解除引用关系
			Node n = head.next;
			head.next = null;
			n.front = null;
			head = n;
		} else if (index < size() - 1) {
			Node node = getIndex(index);
			node.front.next = node.next;
			node.next.front = node.front;
		} else if (index == size() - 1) {
			Node node = getIndex(index);
			foot = node.front;
			node.front.next = null;
			node.front = null;
		}
		count--;
	}

	public void remove(String s) {
		int index = -1;
		for (int i = 0; i < size(); i++) {
			String str = find(i);
			if (s.equals(str)) {
				index = i;
				break;
			}
		}
		if (index >= 0) {
			remove(index);
		}
	}

 以上代码中getIndex方法是得到对应的下标。