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

xiaoxiao2022-07-14 157

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

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 = # 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); } }

微信公众号：

最新回复(0)