链表

来自百度百科

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

链表实现

• Python

class ListNode:
    def __init__(self,val):
        self.val = val
        self.next = None

class SingleLinklist:
    def __init__(self):
        self.__head = None

    ## 判断链表是否为空
    def is_empty(self):
        return self.__head == None

    ## 返回链表的长度, 时间复杂度O(n)
    def length(self):
        cur = self.__head
        count = 0
        while cur != None:
            count += 1
            cur = cur.next
        return count

    ## 尾部插入, 时间复杂度O(n)
    def append(self,val):
        node = ListNode(val)
        if self.__head == None:
            self.__head = node
            return
        cur = self.__head
        while cur.next != None:
            cur = cur.next
        cur.next = node
        return

    ## 头部插入, 时间复杂度O(1)
    def add(self,val):
        if self.__head == None:
            self.__head = ListNode(val)
            return
        cur = self.__head
        self.__head = ListNode(val)
        self.__head.next = cur
        return

    ## 对链表进行遍历, 时间复杂度O(n)
    def travel(self):
        cur = self.__head
        while cur != None:
            print(cur.val,end=',')
            cur = cur.next
        return

    ##  查找链表元素是否存在, 时间复杂度O(n)
    def search(self,val):
        cur = self.__head
        while cur != None:
            if cur.val == val:
                return True
            cur = cur.next
        return False

    ## 在链表中插入元素, 时间复杂度O(n)
    def insert(self,pos,val):
        if pos <= 0:
            self.add(val)
        elif pos > self.length()-1:
            self.append(val)
        else:
            node = ListNode(val)
            count = 0
            cur = self.__head
            while count < pos-1:
                cur = cur.next
                count += 1
            node.next = cur.next
            cur.next = node
        return

    ## 去除链表中元素, 时间复杂度O(n)
    def remove(self,val):
        if self.__head == None: return
        cur = self.__head
        if cur.val == val:
            self.__head = cur.next
            return
        while cur.next != None:
            if cur.next.val == val:
                cur.next = cur.next.next
                return
            cur = cur.next
        return

    ## 链表索引值, 时间复杂度O(n)
    def index(self,num):
        if num <0 or num > self.length()-1:
            return
        cur = self.__head
        count = 0
        while count != num:
            cur = cur.next
            count += 1
        return cur.val

• C++

#include <iostream>
using namespace std;

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x): val(x),next(NULL){}
};


ListNode* createLinkedList(int arr[],int n){
    if(n==0){
        return NULL;
    }
    ListNode* head = new ListNode(arr[0]);
    ListNode* cur = head;
    for (int i=1;i<n;i++){
        cur->next = new ListNode(arr[i]);
        cur = cur->next;
    }
    return head;
}

void printListNode(ListNode* head){
    ListNode* cur = head;
    while (cur){
        cout << cur->val << "->";
        cur = cur->next;
    }
    cout << "NULL" << endl;
    return;
}

int main(){
    int arr[] = {1,2,3,4,5};
    int n = sizeof(arr)/sizeof(int);
    ListNode* head = createLinkedList(arr,n);
    printListNode(head);
    return 0;
}

上述代码为单链表的实现。在ListNode添加一个pre属性即可实现双链表。

双链表实现

class ListNode:
    def __init__(self,val):
        self.val = val
        self.prev = None
        self.next = None

class DoubleLinklist:
    def __init__(self):
        self.__head = None

    ## 判断链表是否为空
    def is_empty(self):
        return self.__head == None

    ## 返回链表的长度, 时间复杂度O(n)
    def length(self):
        cur = self.__head
        count = 0
        while cur != None:
            count += 1
            cur = cur.next
        return count

    ## 尾部插入, 时间复杂度O(n)
    def append(self,val):
        node = ListNode(val)
        if self.__head == None:
            self.__head = node
            return
        cur = self.__head
        while cur.next != None:
            cur = cur.next
        cur.next = node
        node.prev = cur
        return

    ## 头部插入, 时间复杂度O(1)
    def add(self,val):
        if self.__head == None:
            self.__head = ListNode(val)
            return

        cur = self.__head
        self.__head.prev = ListNode(val)
        self.__head = ListNode(val)
        self.__head.next = cur
        return

    ## 对链表进行遍历, 时间复杂度O(n)
    def travel(self):
        cur = self.__head
        while cur != None:
            print(cur.val,end=',')
            cur = cur.next
        return

    ##  查找链表元素是否存在, 时间复杂度O(n)
    def search(self,val):
        cur = self.__head
        while cur != None:
            if cur.val == val:
                return True
            cur = cur.next
        return False

单项循环链表

单链表的一个变形是单向循环链表，链表中最后一个节点的next域不再为None，而是指向链表的头节点。