在单链表中对表头进行插入或者删除时,时间复杂度为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));
}
}