算法与数据结构系列之[链表]

作者: 秦老厮 | 来源:发表于2019-05-23 20:46 被阅读7次

上一篇介绍了线性表的顺序存储结构，顺序存储结构的最大缺点就是插入和删除时需要移除大量元素，如果要插入或删除的数据量很大的话，执行程序的时间就会很长，造成一定的性能消耗，且线性表的顺序存储结构如动态数组，栈和队列，底层依托静态数组，需要通过扩容解决固定容量问题。由于顺序结构的以上问题，链表的优势就凸显出来，链表是最简单的动态数据结构，不需要处理固定容量问题，且插入和删除元素，不需要移动其他元素，所以对于大数据量的频繁插入和删除操作，使用链表的优势就很明显，但链表也丧失了随机访问的能力，所以对于大数据量的频繁查询操作使用顺序存储结构比较好。

C语言代码：

1.LinkedList.c

typedef int ElemType;
typedef int Status;

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

#define ERROR 0
#define OK 1
#define TRUE 1
#define FALSE 0

/**
* 线性表的单链表存储结构
*/
typedef struct Node{
    ElemType data; //数据域
    struct Node *next; //指针域
}Node,*LinkedList;

/**
* 创建带头结点的单链表
* 使用头插法：始终将新节点插入到表头
* @param L
*/
void CreateListHead(LinkedList *L){
    LinkedList p;
    *L =(LinkedList) malloc(sizeof(Node));
    (*L)->next = NULL;  //建立一个带头结点的单链表
    for (int i = 0; i < 10; ++i) {
        p =(LinkedList) malloc(sizeof(Node)); //生成新的节点
        p->data = i;
        p->next = (*L)->next;
        (*L)->next = p;  //插入到表头
    }
}

/**
* 创建带头结点的单链表
* 使用尾插法：始终将新节点插入到表尾
* @param L
*/
void CreateListTail(LinkedList *L){
    LinkedList p,r;
    int i;
    *L =(LinkedList) malloc(sizeof(Node));
    r = *L;  //r为指向尾部的节点
    for (int i = 0; i < 10; ++i) {
        p =(LinkedList) malloc(sizeof(Node));
        p->data = i;
        r->next = p;  //将线性表表尾的节点指向新的节点
        r = p;  //将新插入的节点定义为表尾节点
    }
    r->next = NULL;  //当前链表结束，最后一个节点的指针置为空
}

/**
* 遍历打印链表元素
* @param L
*/
void Display(LinkedList L){
    LinkedList p = L->next;  //将第一个节点赋值给临时节点p
    printf("链表的元素为：");
    if(!p)
        printf("链表为空");
    while (p){
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

/**
* 获取链表的长度
* @param L
* @return
*/
int GetLinkedListSize(LinkedList L){
    int len = 0;
    LinkedList p = L->next;
    while (p){
        len++;
        p = p->next;
    }
    return len;
}

/**
* 判断链表是否为空
* @param L
* @return
*/
int IsLinkedListEmpty(LinkedList L){
    LinkedList p = L->next;
    if(!p)
        return TRUE;
    return FALSE;
}

/**
* 查询单链表，并用e返回L中第i个位置元素的值
* @param L
* @param i
* @param e
* @return
*/
Status GetElement(LinkedList L,int i,ElemType *e){
    int j;
    LinkedList  p;
    p = L->next; //p指向链表的第一个节点
    j = 1;
    while (p && j<i){
        p = p->next;
        j++;
    }
    if(!p || j>i)
        return ERROR; //第i个节点不存在
    *e = p->data;
    return OK;
}

/**
* 给单链表插入元素，在L中第I个元素之前插入新的元素e
* @param L
* @param i
* @param e
* @return
*/
Status LinkedListInsert(LinkedList *L,int i,ElemType e){
    int j;
    LinkedList p,s;
    p = *L;
    j = 1;
    while (p && j<i){  //找到第i-1个节点
        p = p->next;
        j++;
    }
    if(!p || j>i)
        return ERROR; //第i个节点不存在
    s =(LinkedList) malloc(sizeof(Node));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

/**
* 删除单链表L的第i个节点，并用e返回其值
* @param L
* @param i
* @param e
* @return
*/
Status LinkedListDelete(LinkedList *L,int i,ElemType *e){
    int j;
    LinkedList p,q;
    p = *L;
    j = 1;
    while (p->next && j<i){  //找到第i-1个节点
        p = p->next;
        j++;
    }
    if(!(p->next) || j>i)
        return ERROR;   //第i个节点不存在
    q = p->next;
    p->next = q->next;
    *e = q->data;
    free(q);  //让系统回收此节点，释放内存
    return OK;
}

/**
* 删除整个链表
* @param L
* @return
*/
Status ClearLinkedList(LinkedList *L){
    LinkedList p,q;
    p = (*L)->next; //p指向第一个节点
    while (p){
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = NULL; //将头结点的指针域置为空
    return OK;
}

2.LinkedList.h

typedef int ElemType;
typedef int Status;

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

#define ERROR 0
#define OK 1
#define TRUE 1
#define FALSE 0

/**
* 线性表的单链表存储结构
*/
typedef struct Node{
    ElemType data; //数据域
    struct Node *next; //指针域
}Node,*LinkedList;

//创建带头结点的单链表(头插法)
void CreateListHead(LinkedList *L);

//创建带头结点的单链表(尾插法)
void CreateListTail(LinkedList *L);

//遍历打印链表元素
void Display(LinkedList L);

//获取链表长度
int GetLinkedListSize(LinkedList L);

//判断链表是否为空
int IsLinkedListEmpty(LinkedList L);

// 查询单链表，并用e返回L中第i个位置元素的值
Status GetElement(LinkedList L,int i,ElemType *e);

//给单链表插入元素，在L中第I个元素之前插入新的元素e
Status LinkedListInsert(LinkedList *L,int i,ElemType e);

//删除单链表L的第i个节点，并用e返回其值
Status LinkedListDelete(LinkedList *L,int i,ElemType *e);

//删除整个链表
Status ClearLinkedList(LinkedList *L);

3.main.c

//初始化一个具有10个元素的链表(头插法)
LinkedList list;
CreateListHead(&list);
Display(list);
//初始化一个具有10个元素的链表(尾插法)
CreateListTail(&list);
Display(list);
//获取链表长度
int len = GetLinkedListSize(list);
printf("%d",len);
printf("\n");
//判断链表是否为空
int result = IsLinkedListEmpty(list);
printf("%d",result);
printf("\n");
//查询链表某个位置的元素
int num;
int *n = &num;
GetElement(list,6,n);
printf("%d",*n);
printf("\n");
//插入元素
LinkedListInsert(&list,3,16);
Display(list);
//删除元素
int delNum;
int *d = &delNum;
LinkedListDelete(&list,3,d);
Display(list);
printf("%d",*d);
printf("\n");
//删除整个链表
ClearLinkedList(&list);
Display(list);
int result2 = IsLinkedListEmpty(list);
printf("%d",result2);

4.执行结果

链表的元素为：9 8 7 6 5 4 3 2 1 0
链表的元素为：0 1 2 3 4 5 6 7 8 9
10
0
5
链表的元素为：0 1 16 2 3 4 5 6 7 8 9
链表的元素为：0 1 2 3 4 5 6 7 8 9
16
链表的元素为：链表为空
1

java代码：

public class LinkedList<E> {

    private class Node{
        public E e;
        public Node next;

        public Node(E e,Node next){
            this.e = e;
            this.next = next;
        }

        public Node(E e){
            this(e,null);
        }

        public Node(){
            this(null,null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node dummyHead; //链表头结点
    private  int size;

    public LinkedList(){
        this.dummyHead = new Node(null,null);
        this.size= 0;
    }
    //获取链表中元素的个数
    public int getSize(){
        return size;
    }

    //链表是否为空
    public boolean isEmpty(){
        return size == 0;
    }

    //在链表指定的位置添加元素
    public void  add(int index,E e){  //链表实际上是没有索引的概念的，为了便于理解起见，这里引入索引概念，这里索引从0开始，和C语言版的链表区分
        if(index < 0 || index > size){
            throw  new IllegalArgumentException("非法索引");
        }
        Node prev = dummyHead;
        for (int i = 0; i < index ; i++) {
            prev = prev.next;
        }
       /* Node node = new Node(e);
        node.next = prev.next;
        prev.next = node;*/
        prev.next = new Node(e,prev.next);  //此处的代码执行效果等价于上面注释掉的代码
        size++;
    }

    //在链表头添加新的元素
    public void addFirst(E e){
        //1
       /* Node node = new Node(e); //1和2的执行效果等价
        node.next = head;100
        head = node;
        */
       // 2 head = new Node(e,head);
       add(0,e);
    }

    //在链表的末尾添加新的元素
    public void  addLast(E e){
        add(size,e);
    }

    //获取链表指定位置元素
    public E get(int index){
        if(index < 0 || index >= size){
            throw  new IllegalArgumentException("非法索引");
        }
        Node cur = dummyHead.next;
        for (int i = 0; i < index ; i++) {
            cur = cur.next;
        }
        return cur.e;
    }

    //获取链表的第一个元素
    public E getFirst(){
        return get(0);
    }

    //获取链表的最后一个元素
    public E getLast(){
        return get(size-1);
    }

    //修改链表指定位置的元素值
    public void set(int index,E e){
        if(index < 0 || index >= size){
            throw  new IllegalArgumentException("非法索引");
        }
        Node cur = dummyHead.next;
        for (int i = 0; i < index ; i++) {
            cur = cur.next;
        }
        cur.e = e;
    }

    //查找链表是否有元素e
    public boolean contains(E e){
        Node cur = dummyHead.next;
        while (cur != null){
            if(cur.e.equals(e)){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //删除指定位置的链表元素
    public E remove(int index){
        if(index < 0 || index >= size){
            throw  new IllegalArgumentException("非法索引");
        }
        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {  //找到要删除节点的前一个节点
            prev = prev.next;
        }
        Node retNode = prev.next;
        prev.next = prev.next.next;
        retNode.next = null;
        size--;
        return retNode.e;
    }

    //删除链表的第一个元素
    public E removeFirst(){
        return remove(0);
    }

    //删除链表的最后一个元素
    public E removeLast(){
        return remove(size-1);
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        Node cur = dummyHead.next;
        while (cur != null){
            res.append(cur + "->");
            cur = cur.next;
        }
        res.append("NULL");
        return res.toString();
    }


    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < 5; i++) {
            linkedList.addFirst(i);
            System.out.println(linkedList);
        }
        linkedList.add(0,521);
        System.out.println(linkedList);
        linkedList.add(3,521);
        System.out.println(linkedList);
        int num = linkedList.get(2);
        System.out.println(num);
        linkedList.remove(3);
        System.out.println(linkedList);
        linkedList.removeFirst();
        System.out.println(linkedList);
    }
}

微信公众号，点关注不迷路：

qrcode_for_gh_c99ccf9a1b74_258.jpg

算法与数据结构系列之[链表]

C语言代码：

java代码：

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

算法与数据结构