Biegral Blog

在单链表中对表头进行插入或者删除时，时间复杂度为O(1)。

单链表查询指定节点时因为要进行循环查找，平均需要查找N/2次，所以时间复杂度为O(N)。

存储密度=数据占用的存储量/整个结点占用的存储量。根据这个公式可以得出单链表的存储密度为大于1，在空间利用率上面比顺序表要差；

所以可以得出以下结论：单链表一般作为插入或者删除频繁，查询比较少的场景下使用。空间使用率上面是比较顺序表要低。

下面直接上代码举例说明：

public class LinkedList {
	private class Node {//定义一个节点类
		private Object value;
		private Node next = null;
		Node(Object value) {
			this.value = value;
		}
	}
	private Node first = null;//定义First节点对象
	public void insertFirst(Object obj) {//在first节点前加入值为obj的节点
		Node node = new Node(obj);
		node.next = first;
		first = node;
	}

	public void insertFirstValue(Object value,Object obj) throws Exception {
		//在单链表中值为value的节点前加入值为obj的节点
		if(first==null){
			throw new Exception("LinkedList is empty!");
		}else if(find(value)==null){
			throw new Exception("not find this value!");
		}
		Node node=new Node(obj);
		if(first.value.equals(value)){	
			node.next=first;
			first=node;
		}else{
			Node pre=first;
			Node cur=first.next;
			while(cur!=null){
				if(cur.value.equals(value)){
					node.next=cur;
					pre.next=node;
				}
				pre=cur;
				cur=cur.next;
			}
		}
	}
	
	public void insertEndValue(Object value,Object obj) throws Exception{
		//在单链表中值为value的节点后加入值为obj的节点
		if(first==null){
			System.out.println("LinkedList is empty!");
		}else if(find(value)==null){
			System.out.println("not find this value!");
		}
		Node node=new Node(obj);
		if(first.value.equals(value)){
			node.next=first.next;
			first.next=node;
		}else{	
			Node pre=first;
			Node cur=first.next;
			while(cur!=null){
				if(cur.value.equals(value)){
					node.next=cur.next;
					cur.next=node;
				}
				pre=cur;
				cur=cur.next;
			}
		}	
	}
	public Object deleteFirst() throws Exception {//删除First节点
		if (first == null)
			throw new Exception("empty!");
		Node temp = first;
		first = first.next;
		return temp.value;
	}

	public Object find(Object obj) throws Exception {//查询单链表中是否有这么一个值，并把结果返回
		if (first == null)
			throw new Exception("LinkedList is empty!");
		Node cur = first;
		while (cur != null) {
			if (cur.value.equals(obj)) {
				return cur.value;
			}
			cur = cur.next;
		}
		return null;
	}

	public void remove(Object obj) throws Exception {//删除单链表中值为obj的节点对象。
		if (first == null)
			throw new Exception("LinkedList is empty!");
		if (first.value.equals(obj)) {
			first = first.next;
		} else {
			Node pre = first;
			Node cur = first.next;
			while (cur != null) {
				if (cur.value.equals(obj)) {
					pre.next = cur.next;
				}
				pre = cur;
				cur = cur.next;
			}
		}
	}

	public boolean isEmpty() {//判断单链表是否为空
		return (first == null);
	}

	public void display() {//打印单链表中的所有数据
		if (first == null)
			System.out.println("empty");
		Node cur = first;
		while (cur != null) {
			System.out.print(cur.value.toString() + " -> ");
			cur = cur.next;
		}
		System.out.print("\n");
	}

	public static void main(String[] args) throws Exception {
		LinkedList ll = new LinkedList();
		ll.insertFirst(4);
		ll.insertFirst(3);
		ll.insertFirst(2);
		ll.insertFirst(1);
		ll.display();
		//ll.insertFirstValue(1,10);
		ll.insertEndValue(1,10);
		ll.display();
//		ll.deleteFirst();
//		ll.display();
//		ll.remove(3);
//		ll.display();
//		System.out.println(ll.find(1));
//		System.out.println(ll.find(4));
	}
}