单链表

链表应该是IT领域比较重要的一种数据结构了,几乎可以在各个操作系统,各种编程语言,各个软件中都可见到。

比如Mysql的三种链表用于进行数据页分配,脏页处理以及缓存淘汰;操作系统使用链表管理页帧,Redis采用大量的链表结果,比如列表底层使用的双向链表,发布订阅,客户端状态等等。

之所以受欢迎,主要还是得益于首先其不需要连续的内存空间,此外其动态插入和删除的效率比较高,相对于数组,其不必每次操作都要同时移动其他数据。虽然其除了存储值本身外,还存储指针,看似比较浪费空间,但更多时候都是瑕不掩瑜,其高校的数据处理要掩盖其内存浪费的劣势。

1、单链表介绍

2、单链表的操作

  • 创建;
  • 删除;
  • 插入;
  • 反转;
  • 寻找两个单链表的第一个公共结点
  • 倒数第k个结点

Python实现:

class Node:

    def __init__(self,data=None):
        self.data, self.next = data,None


class LinkList:

    def __init__(self):
        self.tail = self.head = Node()


    def isEmpty(self):
        if self.head.next is None:
            return True
        return False

    @property
    def length(self):
        length = 0
        cur = self.head
        while cur.next is not None:
            length += 1
            cur = cur.next
        return length

    def insert(self,value,index=-1):
        if index > self.length:
            raise ValueError('the index is longer than length')
        node = Node(value)
        cur_node,cur_pos = self.head,0
        if self.length == 0 or index == self.length or index == -1 :
           self.tail.next = node
           self.tail = self.tail.next
        else:
            while cur_pos < index:
                cur_node = cur_node.next
                cur_pos += 1
            node.next = cur_node.next
            cur_node.next = node

    def remove(self,index=-1):
        if index > self.length:
            raise ValueError('the index is longer than length')
        if index == self.length or index == -1:
            cur = self.head
            while cur.next != self.tail:
                cur = cur.next
            cur.next = None
            self.tail = cur
        pre_node,cur_pos = self.head,0
        while cur_pos < index - 1:
            pre_node = pre_node.next
            cur_pos += 1
        pre_node.next = pre_node.next.next



    def iterprint(self):
        cur = self.head
        while cur != self.tail:
            cur = cur.next
            print cur.data


if __name__ == "__main__":
    linklist = LinkList()
    linklist.insert(3)
    linklist.insert(5)
    linklist.insert(8)
    linklist.insert(4,1)
    linklist.iterprint()
    linklist.remove(2)
    linklist.iterprint()

JAVA实现:

@Data
class Node<E> {

    private E value;

    private Node<E> next;
}

public class SingleLinkList<E> {

    @Getter
    private int size;

    private Node<E> head;

    private Node<E> tail;

    SingleLinkList(){
        this.size = 0;
        head = new Node<E>();
        tail = new Node<E>();
        head.setValue(null);
        head.setNext(null);
        tail.setValue(null);
        tail.setNext(null);
    }

    public  boolean insert(E x){
        Node<E> node = new Node<>();
        node.setValue(x);
        if (size == 0){
            head.setNext(node);
            node.setNext(tail);
        }else {
            Node<E> cur = head;
            while (cur.getNext() != tail){
                cur = cur.getNext();
            }
            cur.setNext(node);
            node.setNext(tail);
        }
        size++;
        return true;
    }

    public  boolean remove(int index){
        if (index > size - 1)
            return false;
        int curIndex = 0;
        Node<E> curNode = head.getNext();
        while (curIndex < index -1 && curNode.getNext() != tail){
            curIndex ++;
            curNode = curNode.getNext();
        }
        if (curIndex == index - 1){
            Node<E> afterCurNode = curNode.getNext();
            curNode.setNext(afterCurNode.getNext());
            afterCurNode.setNext(null);
            afterCurNode.setValue(null);
            return true;
        }
        return false;
    }

    public String toString(){
        if (size == 0){
            return "";
        }
        StringBuilder stringBuilder = new StringBuilder();
        Node<E> e = head.getNext();
        while (e!=tail){
            stringBuilder.append(e.getValue());
            e = e.getNext();
        }
        return stringBuilder.toString();
    }

    /**
     * 链表反转
     */
    public void reverse(){
        if (size == 0){
            return;
        }else {
            Node<E> pre = head;
            Node<E> cur = head.getNext();
            while(cur != null){
                Node<E> next = cur.getNext();
                cur.setNext(pre);
                pre = cur;
                cur = next;
            }
            Node<E> tmp = head;
            head = tail;
            tail = tmp;
        }

    }


    public static void main(String[] args){
        SingleLinkList<Integer> singleLinkList = new SingleLinkList<Integer>();
        singleLinkList.insert(3);
        singleLinkList.insert(2);
        singleLinkList.insert(4);
        singleLinkList.insert(1);
        singleLinkList.insert(15);
        System.out.println(singleLinkList);
        System.out.println(singleLinkList.remove(4));
        System.out.println(singleLinkList);
        singleLinkList.reverse();
        System.out.println(singleLinkList);

    }

}

代码实现(C语言):

#include<stdio.h>
#include<stdlib.h>
#include<time.h>


//定义结构体
typedef struct node {
    int data;
    struct node *next;
}Node;


void print_chain(Node *L)
{
    if(L==NULL||L->next==NULL)
        return;
    Node *cur = L->next;
    while(cur!=NULL)
    {
        printf("%d,",cur->data);
        cur = cur->next;
    }
    printf("\n");
}



 /*

    创建的链表第一个元素不存储数据,只有指向第一个节点的指针。
    其中head是头指针,r是尾指针。
    随机数使用rand函数生成。 
 */

Node *create_linkedlist(int n)
{
    int i;
    srand(time(0));
    Node *head;
    head = (Node*)malloc(sizeof(Node));
    if(head==NULL)
        return;
    head->next = NULL;
    Node *r = head;
    Node *p;
    for(i=0;i<n;i++)
    {
        p = (Node*)malloc(sizeof(Node));
        if(p==NULL)
            return;
        p->data = i+1;
        r->next = p;
        r = p;
    }
    r->next = NULL;
    return head;
}

int get_length(Node *L)
{
    int length = 0;
    if(L==NULL)
        return 0;
    Node *cur = L;
    while(cur!=NULL)
    {
        length += 1;
        cur = cur->next;
    }
    return length;
}

//删除结点
Node *delete_node(Node *L,int index)
{
    //如果结点位置超过链表长度,就直接退出。
    int length = get_length(L);
    if(index<1 || index >length)
        return;
    Node *cur = L;
    int i = 1;
    while(cur->next!=NULL && i<index)
    {
        cur = cur->next;
        ++i;
    }
    //将删除结点的前一个结点的next指针直接指向所删除结点的下一个元素。
    Node *p = cur->next;
    cur->next = p->next;
    printf("delete item:%d\n",p->data);
    free(p);
    return L;
}

 //插入结点
Node *insert_node(Node *L,int index,int data)
{
    int i = 1;
    Node *insertNode = (Node*)malloc(sizeof(Node));
    if(insertNode==NULL)
        return;
    Node *p = L;
    while(p->next!=NULL && i<index)
    {
        p = p->next;
        ++i;
    }
    if(!p || i>index)
        return;
    /*要插入的位置index的结点是p,其下一个结点是q,现将p的next指针指向要插入的结点,然后将插入结点的next指针指向q。
    insertNode->data = data;
    insertNode->next = p->next;
    p->next = insertNode;
    return L;
}

  Node *Reverse(Node *L)
  {
    Node *Pre = NULL;
    Node *cur = L->next;
    while(cur!=NULL)
    {
        Node *q = cur->next;
        cur->next = Pre;
        Pre = cur;
        cur = q;
    }
    Node *ReverseHead = (Node*)malloc(sizeof(Node));
    ReverseHead->next = Pre;
    return ReverseHead;
 }


//寻找两个单链表的第一个公共结点
Node *find_first_common_node(Node* L1,Node* L2)
{
    int L1Length = get_length(L1);
    int L2Length = get_length(L2);
    int length_diff = L1Length - L2Length;
    /*首先计算两个链表的长度插,让长的指针先走,走了他们长度差的步数之后,让两指针同时移动,目的是为了保证他俩可以同时到达第一个公共结点。*/
    Node *LinkLong = L1;
    Node *LinkShort = L2;
    if(length_diff<0)
    {
        length_diff=L2Length-L1Length;
        LinkLong = L2;
        LinkShort = L1;
    }
    for(int i=0;i<length_diff;i++)
        LinkLong = LinkLong->next;
    while(LinkLong!=NULL && LinkShort!=NULL && LinkLong->data!=LinkShort->data)
    {
        LinkLong = LinkLong->next;
        LinkShort = LinkShort->next;
    }
    return LinkLong;
}


 //寻找倒数第k个结点
 /*倒数第K个结点,也就是正数n-k+1,但是总长度n需要遍历整个链表得到,因此这里使用两个指针,使两个指针步长相差k-1,当前一个指针走到了链表尾部,那么后一个指针就是所找的位置*/
 Node* find_reverse_k_node(Node* L,int k)
{
    Node *p = L;
    Node *q = L;
    for(int i=1;i<k;i++)
        q = q->next;
    while(q->next!=NULL)
    {
        p = p->next;
        q = q->next;
    }
    return p;
}


int main(void)
{
    int n = 10;
    Node *chain = create_linkedlist(n);
    print_chain(chain);
    printf("\n");
    Node *del = delete_node(chain,3);
    print_chain(del);
    printf("\n");
    Node *ins = insert_node(chain,3,100);
    print_chain(ins);
    return 0;
}


输出:
    1,2,3,4,5,6,7,8,9,10,

    delete item:3
    1,2,4,5,6,7,8,9,10,

    1,2,100,4,5,6,7,8,9,10,
    10,9,8,7,6,5,4,100,2,1,

时间复杂度分析:如果是要寻找第i个结点的元素,那链表和数组的时间复杂度是一样,但要向第i个位置添加n个结点,链表明显占优。数组插入一个元素,要移动其他1-n个元素,时间复杂度为O(1),链表只需要改变前后元素的指针,时间复杂度为O(1)。

--------EOF---------
本文微信分享/扫码阅读