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

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

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

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

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

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

3. Java实现单链表：

// 单向链表
public class SingleLinkedList<E> {
	private Node<E> head; // 头结点
	private int size; // 链表长度

	// 建立一个空链表
	public SingleLinkedList() {
		head = null;
		size = 0;
	}
	
	// 在链表尾部插入
	public boolean add(E data){
		Node<E> newNode = new Node<E>(data);
		if(isEmpty()){
			head = newNode;
		}else{
			Node<E> tail = get(size);
			tail.setNext(newNode);
		}
		size++;
		return true;
	}

	// 插入指定位置的结点
	public boolean insert(int position, E data) {
		if(position >= 1 && (position <= size + 1)){
			Node<E> newNode = new Node<E>(data);
			if(isEmpty() || position == 1){ // 链表为空或在头结点前插入
				newNode.setNext(head);
				head = newNode;
			}else{ // 在中间位置插入
				Node<E> preNode = get(position - 1); // 获取position的前一结点
				Node<E> originalNode = preNode.getNext(); // 获取未插入结点时position位置对应结点 
				preNode.setNext(newNode);
				newNode.setNext(originalNode);
			}
			size++;
			return true;
		}
		return false;
	}

	// 删除指定位置的结点
	public E delete(int position) { 
		E result = null;
		if(position >= 1 && position <= size){
			if(position == 1){ // 删除头结点
				result = head.getData();
				Node<E> afterHead = head.getNext();
				head = afterHead;
			}else{ // 删除其他结点
				Node<E> preNode = get(position - 1); // 获取待删除结点的前一结点
				Node<E> curNode = preNode.getNext(); // 获取待删除结点
				result = curNode.getData();
				preNode.setNext(curNode.getNext()); // 将待删除结点前一结点指向待删除结点下一结点
			}
			size--;
		}
		return result;
	}
	
	// 获取某个位置的结点
	public Node<E> get(int position){
		Node<E> targetNode = null;
		if(!isEmpty() && position >= 1 && position <= size){ 
			targetNode = head;
			for(int i = 1; i < position ; i++){
				targetNode = targetNode.getNext(); // 循环获取对应位置的结点
			}
		}
		return targetNode;
	}
	
	// 获取链表的长度
	public int getSize(){
		return size;
	}
	
	// 判断链表是否为空
	public boolean isEmpty(){
		return size == 0;
	}
	
	// 打印链表数据
	public void display(){
		Node<E> node = head;
		System.out.print("单链表: ");
		for(int i = 0; i < size; i++){
			System.out.print(" " + node.getData());
			node = node.getNext();
		}
		System.out.println("");
	}
}

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

	public Node() {
	}

	public Node(E data) {
		this.data = data;
	}
	
	public Node(E data,Node<E> next) {
		this.data = data;
		this.next = next;
	}

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

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

	public E getData() {
		return data;
	}

	public void setData(E data) {
		this.data = data;
	}

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

// 测试类
public class Main {
	public static void main(String[] args) {
		SingleLinkedList<Integer> circular = new SingleLinkedList<Integer>();
		circular.add(1);
		circular.add(2);
		circular.add(3);
		circular.insert(4,4);
		circular.insert(5,5);
		circular.insert(6,6);
		circular.delete(3);
		circular.delete(5);
		circular.display();
		System.out.println("链表的长度为:  " + circular.getSize());
	}
}

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

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

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