本文主要是介绍单链表类，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.单链表类之java实现（结点类Node见单链表分析）
package linearList;public class SinglyLinkedList<E> implements LList<E>{protected Node<E> head;//头指针，指向单链表第一个结点/** 构造空单链表*/public SinglyLinkedList(){this.head = null;}/** 构造指定头指针的单链表*/public SinglyLinkedList(Node<E> head){this.head = head;}/** 判断单链表是否为空*/public boolean isEmpty(){return this.head == null;}/** 返回单链表长度,遍历算法*/public int length(){int count = 0;Node<E> p = this.head;while(p!=null){p = p.next;count++;}return count;}/** 返回序号为index的对象*/public E get(int index){if(this.head!=null&&index>=0){Node<E> p = this.head;int i = 0;while(p!=null&&i<index){i++;p = p.next;}if(p!=null){return (E)p.data;}}return null;}/** 设置序号为index的对象的值为element，返回原对象*/public E set(int index,E element){if(this.head!=null&&index>=0&&element!=null){Node<E> p = this.head;int i = 0;while(p!=null&&i<index){i++;p = p.next;}if(p!=null){E old = (E)p.data;p.data = element;return old;}}return null;}/** 插入element对象，插入位置序号为index*/public boolean add(int index,E element){if(element==null){return false;}/** 头插入*/if(this.head==null||index<=0){Node<E> q = new Node<E>(element);//给将要插入的element建立结点，方便操作q.next = this.head;this.head = q;}else{//单链表不为空，并且index>=1Node<E> p = this.head;int i = 0;while(p.next!=null&&i<index-1){//寻找插入位置i++;p = p.next;}Node<E> q = new Node<E>(element);q.next = p.next;p.next = q;}return true;}public boolean add(E element){return add(this.length(),element);}/** 移除序号为index的对象，返回被移除的对象*/public E remove(int index){E old = null;if(this.head!=null&&index>=0){if(index==0){//头删除old = (E)this.head.data;this.head = this.head.next;}else{//中间/尾删除int i = 0;Node<E> p = this.head;while(p.next!=null&&i<(index-1)){i++;p = p.next;}if(p.next!=null){old = (E)p.next.data;p.next = p.next.next;}}}return old;}/** 清空单链表*/public void clear(){this.head = null;}/** 返回所有元素对应的字符串*/public String toString(){String str = "(";Node<E> p = this.head;while(p!=null){str += p.data.toString();p = p.next;if(p!=null){str += ",";}}return str + ")";}
}
单链表是一种顺序存储结构，不是随机存储结构。访问第i个结点，必需从head开始，沿着链的方向逐个查找，进行i次的p=p.next操作，平均进行n/2次，因此，get和set方法的时间复杂度都是O(n)
isEmpty()方法的时间复杂度是O(1)，length()方法要遍历整个单链表，时间复杂度是O(n)。
在指定的结点之后插入新结点的操作十分方便，时间复杂度是O(1);如果要在指定结点的前面插入新结点，就必须首先找到指定结点的前驱结点，然后把新结点插在该结点之后，这个过程需要遍历部分单链表，花费时间视插入的位置而定，最后的情况就是新结点插在单链表的最后，此时时间复杂度为O(n);同理，删除操作也如此。
从上面我们可以看出有时候单链表的效率不是太高，这就需要我们去改进，这也是为什么出现了很多的链表形式的原因，之后我会一一介绍。
这篇关于单链表类的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
