【数据结构】链表

链表是数据结构课程的第一讲，也是最为简单的数据结构。其基本结构是一个包含有值和另一个节点地址或索引的对象。逐个对象因为上一级（前驱）的索引而一一相连，形成了一个链状的线性结构。链表可以灵活地增加或者减少节点的个数，当时需要增加时，临时向系统申请一块内存，并建立索引。因此与数组不同，链表的节点可以分布于内存中的任何地方，它们并不是一个有序相邻放置的结构尽管在程序应用上，我们将其视为一个线性表。因为节点放置的分散，所以在访问时，指针势必会高频率跳转，这也使得访问的耗时在硬件上层面上是大于数组的访问的。

链表根据索引的方向和个数不同，可以建立从前至后的单向链表，前后相互索引的双向链表，起始和结尾相连的循环链表等等（如下图）。

其结构灵活足以满足各类工业开发，并且也是面试中考官们乐此不疲的话题点。本文讲给出单向链表的代码实现。

代码实现

单向链表类型中保存有首节点地址作为头指针，这是链表的入口地址。如下给出链表类定义

class LinkedList{
	Node head;
}

如下代码给出一个单向链表节点的定义

class Node {
	int value;
	Node next;

	public Node(int value) {
		this.value = value;
	}
}

如下代码给出链表的增删改查操作的成员函数定义。

插入操作：传入插入值

public void insert(int value) {
		if (head == null)
			head = new Node(value);
		else {
			Node pointer = head;
			while (pointer.next != null)
				pointer = pointer.next;
			pointer.next = new Node(value);
		}
	}

public boolean delete(int position) {
		/**
		 * 参数验证，必不可少
		 */
		if (position < 0)
			return false;
		if (head == null)
			return false;

		if (position == 0) {
			if (head != null)
				head = head.next;
		} else {
			int n = 0;
			Node previous = head;
			Node current = head.next;
			while (current != null) {
				previous = current;
				current = current.next;
				n++;
				if (n == position - 1) {
					if (current != null) {
						previous.next = current.next;
						current.next = null;
					} else
						previous.next = null;
				}
			}
			if (n < position - 1)
				return false;
		}
		return true;
	}

查找：获取某一索引的值

public int get(int position) throws NoSuchElementException{
		Node current = head;
		int n = 0;
		while(current != null){
			if(position == n) return current.value;
			current = current.next;
			n++;
		}
		throw new NoSuchElementException();
	}

查找：验证是否包含某一值

public int contains(int value) {
		Node current = head;
		int n = 0;
		while (current != null) {
			if (current.value == value)
				return n;
			current = current.next;
			n++;
		}
		return -1;
	}

修改：修改某一索引的值

	public void set(int position,int value) {
		Node current = head;
		int n = 0;
		while(current != null){
			if(n == position) current.value = value;
			current = current.next;
			n++;
		}
	}

由于单向链表的插入只发生在尾部，因此链表元素的存储是以插入顺序保存的，所谓先来后到。对于单向链表的排序，需要考虑到其正向索引可行而反向索引局限的问题，因此冒泡，插入排序等将很难实现。我在学习链表时，课本推荐选择排序，这里给出单线链表选择排序的参考代码

	/**
	 * 选择排序
	 */
	public void selectionSort() {
		if (head != null || head.next != null) {
			Node current = head;
			Node next = null;
			Node minimum = null;
			int temp = 0;
			
			while (current != null) {
				next = current.next;
				minimum = current;
				while (next != null) {
					if (next.value < minimum.value) {
						minimum = next;
					}
					next = next.next;
				}
				
				temp = current.value;
				current.value = minimum.value;
				minimum.value = temp;
				
				current = current.next;
				minimum = current;
			}
		}
	}

class Node {
	int value;
	Node next;

	public Node(int value) {
		this.value = value;
	}
}

class LinkedList {
	Node head;

	/**
	 * 插入数值
	 */
	public void insert(int value) {
		if (head == null)
			head = new Node(value);
		else {
			Node pointer = head;
			while (pointer.next != null)
				pointer = pointer.next;
			pointer.next = new Node(value);
		}
	}

	/**
	 * 删除指定位置的节点
	 */
	public boolean delete(int position) {
		/**
		 * 参数验证，必不可少
		 */
		if (position < 0)
			return false;
		if (head == null)
			return false;

		if (position == 0) {
			if (head != null)
				head = head.next;
		} else {
			int n = 0;
			Node previous = head;
			Node current = head.next;
			while (current != null) {
				previous = current;
				current = current.next;
				n++;
				if (n == position - 1) {
					if (current != null) {
						previous.next = current.next;
						current.next = null;
					} else
						previous.next = null;
				}
			}
			if (n < position - 1)
				return false;
		}
		return true;
	}

	/**
	 * 修改指定节点的值
	 */
	public void set(int position,int value) {
		Node current = head;
		int n = 0;
		while (current != null) {
			if (n == position)
				current.value = value;
			current = current.next;
			n++;
		}
	}
	
	/**
	 * 查找某一索引的值
	 */
	public int get(int position) throws NoSuchElementException{
		Node current = head;
		int n = 0;
		while(current != null){
			if(position == n) return current.value;
			current = current.next;
			n++;
		}
		throw new NoSuchElementException();
	}
	
	/**
	 * 验证是否包含某一值
	 */
	public int contains(int value) {
		Node current = head;
		int n = 0;
		while (current != null) {
			if (current.value == value)
				return n;
			current = current.next;
			n++;
		}
		return -1;
	}

	/**
	 * 选择排序
	 */
	public void selectionSort() {
		if (head != null || head.next != null) {
			Node current = head;
			Node next = null;
			Node minimum = null;
			int temp = 0;
			
			while (current != null) {
				next = current.next;
				minimum = current;
				while (next != null) {
					if (next.value < minimum.value) {
						minimum = next;
					}
					next = next.next;
				}
				
				temp = current.value;
				current.value = minimum.value;
				minimum.value = temp;
				
				current = current.next;
				minimum = current;
			}
		}
	}
}

如上是一个基本链表的实现过程，当然这里是针对整型的链表，根据需要可以在链表中加入长度标量来记录当前链表的长度，也可以加入记录最大最小值的变量等。

（编辑：ASP站长网）