狂言数据结构二：线性表的链式存储结构（单链表）

大话数据结构二：线性表的链式存储结构（单链表）

1. 线性表的链式存储结构：指的是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的，这就意味着这些数据元素可以存在内存未被占用的任意位置。

2. 结点：结点由存放数据元素的数据域和存放后继结点地址的指针域组成。

1.）顺序存储结构中，每个数据元素只需要存数据元素的信息就可以了。

2.）链式存储结构中，除了要存储数据元素信息外，还要存储它的后继元素的存储地址。

3.）链表中第一个结点叫头结点，它的存储位置叫做头指针，它的数据域可以不存储任何信息，链表的最后一个结点指针为空。

3. Java实现单链表：

public class SingleLinkedList<E> {
	private Node<E> head; // 每个链表都存有一个空值的头结点。
	private Node<E> tail; // 链表的最后一个结点，尾结点(该属性可无)。
	private int size = 0; // 当前链表中的节点数目。

	// 建立一个空链表（建立其头结点）。
	public SingleLinkedList() {
		head = new Node<E>();
		tail = head;
	}

	// 在链表的尾部插入数据
	public boolean add(E e) {
		Node<E> node = new Node<E>(e); // 将要插入的值封装成一个节点。
		tail.setNext(node); // 将待插入结点放到尾结点的下一个结点。
		tail = tail.getNext(); // 将新增加的结点设为尾节点。
		size++; // 链表大小增1。
		return true;
	}

	// 插入指定位置的结点
	public boolean insert(int index, E e) {
		validateIndex(index);
		Node<E> newNode = new Node<E>(e); // 将要插入的值封装成一个节点。
		if (index == 0) {
			Node<E> curNode = head.getNext();
			head.setNext(newNode);
			newNode.setNext(curNode);
		}else{
			Node<E> preNode = getNode(index - 1); // 获取待插入结点的前一个结点
			Node<E> nextNode = preNode.getNext(); // 获取待插入结点的下一个结点
			newNode.setNext(nextNode);
			preNode.setNext(newNode);
		}
		size++;
		return true;
	}

	// 删除指定位置的结点
	public boolean delete(int index) {
		Node<E> curNode = null;
		if (index == 0) {
			curNode = head.getNext();
			Node<E> nextNode = curNode.getNext();
			head.setNext(nextNode);
		} else {
			validateIndex(index);
			curNode = getNode(index); // 获取待删除节点。
			Node<E> preNode = getNode(index - 1); // 获取待删除节点的前一个结点。
			preNode.setNext(curNode.getNext()); // 将待删除节点的前一个结点的下一个结点指向待删除节点的下一个结点。
		}
		curNode.setNext(null); // 将待删除节点的下一结点置空。
		size--;
		return true;
	}
	
	// 获取指定位置的结点
	private Node<E> getNode(int index) {
		validateIndex(index);
		Node<E> node = head;
		for (int p = 0; p <= index; p++) {
			node = node.getNext();
		}
		return node;
	}
	
	// 验证下标值是否合法，非法时抛出异常。
	private void validateIndex(int index) {
		if (index < 0 || index > size) {
			throw new IndexOutOfBoundsException("无效的下标：" + index);
		}
	}
	
	// 获取指定位置的结点的值
	public E get(int index) {
		validateIndex(index);
		Node<E> node = getNode(index);
		return node.getValue();
	}

	// 设置指定位置结点的值。
	public void set(int index, E e) {
		validateIndex(index);
		Node<E> node = getNode(index);
		node.setValue(e);
	}

	// 获取链表的大小。
	public int size() {
		return size;
	}
	
	public void display(){
		if (size == 0) {
			System.out.println("list is null");
		} else {
			for (Node<E> p = head.getNext(); p != null; p = p.getNext())
				System.out.println(p.getValue());
		}
	}
}

// 结点类，包含结点的数据和指向下一个节点的引用
public class Node<E> {
	private E nodeValue;  // 数据域
	private Node<E> next;  // 指针域保存着下一节点的引用

	public Node() {
	}

	public Node(E nodeValue) {
		this.nodeValue = nodeValue;
	}

	public void setNext(Node<E> next) {
		this.next = next;
	}

	public Node<E> getNext() {
		return next;
	}

	public E getValue() {
		return nodeValue;
	}

	public void setValue(E nodeValue) {
		this.nodeValue = nodeValue;
	}

	@Override
	public String toString() {
		return "" + nodeValue;
	}
}

// 测试类
public class Main {
	public static void main(String[] args) {
		SingleLinkedList<String> t = new SingleLinkedList<String>();
		t.add("A");
		t.add("B");
		t.add("C");
		t.insert(0, "D");
		t.insert(2, "E");
		t.delete(4);
		t.delete(0);
		t.display();
		System.out.println(t.size());
	}
}

4. 单链表结构和顺序存储结构优缺点：

1.）若线性表需要频繁查找，很少进行插入和删除操作，宜采用顺序存储结构，若需要频繁插入和删除时，宜采用单链表结构。

2.）当线性表的元素个数变化较大或者根本就不知道多大时，最好用单链表结构，这样可以不需要考虑存储空间的大小问题。单链表所占大小和位置是不需要预先分配划定的，可以根据系统的情况和实际的需求即时生成。