数据结构-链表(一)

简介: 链表(Linked List)是一种常见的数据结构,用于存储和组织数据。与数组不同,链表的元素(节点)在内存中不必连续存储,而是通过指针链接在一起。链表由多个节点组成,每个节点包含两部分:数据(存储实际的元素值)和指针(指向下一个节点的引用)。链表的第一个节点称为头节点,最后一个节点称为尾节点,尾节点的指针通常指向空值(null)。

一、链表简介

链表(Linked List)是一种常见的数据结构,用于存储和组织数据。与数组不同,链表的元素(节点)在内存中不必连续存储,而是通过指针链接在一起。


链表由多个节点组成,每个节点包含两部分:数据(存储实际的元素值)和指针(指向下一个节点的引用)。链表的第一个节点称为头节点,最后一个节点称为尾节点,尾节点的指针通常指向空值(null)。


下面是链表的一些基本特点和操作:


  1. 链表的优点:


  1. 动态性:链表的长度可以根据需要动态增长或缩小,不需要预先分配固定大小的空间。
  2. 插入和删除操作高效:相比数组,链表在插入和删除元素时不需要移动其他元素,只需修改指针的指向。


  1. 链表的缺点:


  1. 非随机访问:链表中的元素并不连续存储,因此无法像数组那样通过索引直接访问元素,需要遍历链表来查找指定位置的元素。
  2. 额外的空间开销:链表需要额外的指针来存储节点之间的链接,相比数组会占用更多的内存空间。


  1. 常见类型的链表:


1.单向链表(Singly Linked List):每个节点包含一个指针,指向下一个节

8a34744571ee4cd79da169aec7712e6c.png

  1. 双向链表(Doubly Linked List):每个节点包含两个指针,分别指向前一个节点和后一个节点。

8b709312c53c40ebaede9c3a28ce02ce.png


3.循环链表(Circular Linked List):尾节点的指针指向头节点,形成一个循环。

3b49636a3eac4abcac08d91dd392d650.png


4.常见的链表操作:


  1. 遍历链表:从头节点开始,依次访问每个节点。
  2. 插入节点:将新节点插入到链表的指定位置,涉及修改指针的指向。
  3. 删除节点:从链表中移除指定节点,同样需要修改指针的指向。


链表在实际应用中具有广泛的用途,例如实现栈、队列、图等数据结构,以及处理大数据集合、缓存管理等场景。


二、相关算法题:

1.移除链表元素

给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点


输入:head = [1,2,6,3,4,5,6], val = 6

输出:[1,2,3,4,5]

3dc46cebbeaf4a7f8728bf02af2c23c4.png

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        # 创建虚拟头部节点以简化删除过程
        dummy_head = ListNode(next = head) 
        # 定义当前节点
        current=dummy_head
        while current.next: # 只要当前节点有后继就循环
                if current.next.val==val:
                        current.next=current.next.next
                else:
                    current=current.next
        reuturn dummy_head.next


2.设计链表

你可以选择使用单链表或者双链表,设计并实现自己的链表。


单链表中的节点应该具备两个属性:val 和 next 。val 是当前节点的值,next 是指向下一个节点的指针/引用。


如果是双向链表,则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。


实现 MyLinkedList 类:


  • MyLinkedList() 初始化 MyLinkedList 对象。
  • int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效,则返回 -1 。
  • void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后,新节点会成为链表的第一个节点。
  • void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
  • void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度,那么该节点会被追加到链表的末尾。如果 index 比长度更大,该节点将 不会插入 到链表中。
  • void deleteAtIndex(int index) 如果下标有效,则删除链表中下标为 index 的节点。
  • 输入

["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]

[[], [1], [3], [1, 2], [1], [1], [1]]

输出

[null, null, null, null, 2, null, 3]


解释

MyLinkedList myLinkedList = new MyLinkedList();

myLinkedList.addAtHead(1);

myLinkedList.addAtTail(3);

myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3

myLinkedList.get(1);              // 返回 2

myLinkedList.deleteAtIndex(1);    // 现在,链表变为 1->3

myLinkedList.get(1);              // 返回 3

class ListNode:
    def __init__(self,val=0,next=None):
        self.val=val
        self.next=next
class MyLinkedList:
    def __init__(self):
         self.dummy_head = ListNode()
         self.size = 0
    def get(self, index: int) -> int:
         if index<0 or index>=self.size:
            return -1
         current=self.dummy_head.next
         for i in range(index):
            currtent=current.next
         print(currtent.val)
         return current.val
    def addAtHead(self, val: int) -> None:
         self.dummy_head.next=ListNode(val,self.dummy_head.next)
         self.size+=1
    def addAtTail(self, val: int) -> None:
         current = self.dummy_head
         while current.next:
            current=current.next
         current.next=ListNode(val)
         self.size+=1
    def addAtIndex(self, index: int, val: int) -> None:
         if index <0 or index >self.size:
            return
         current=self.dummy_head
         for i in range(index):
            current=current.next
         current.next=ListNode(val,current.next)
         self.size+=1
    def deleteAtIndex(self, index: int) -> None:
         if index <0 or index >=self.size:
            return
         current=self.dummy_head
         for i in range(index):
            current=current.next
         current.next=current.next.next
         self.size-=1
# Your MyLinkedList object will be instantiated and called as such:
obj = MyLinkedList()
obj.addAtHead(1)
obj.addAtTail(3)
obj.addAtIndex(1,2)
obj.get(1)
obj.deleteAtIndex(1)
obj.get(1)
# ["MyLinkedList","addAtHead","addAtTail","addAtIndex","get","deleteAtIndex","get"]
# [[],[1],[3],[1,2],[1],[1],[1]]


3.反转链表

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。


输入:head = [1,2,3,4,5]

输出:[5,4,3,2,1]


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None,pre=None):
        self.val = val
        self.next = next
class Solution:
    def reverseList(head):
        cur = head
        pre=None
        while cur:
            temp=cur.next
            cur.next=pre
            pre=cur
            cur=temp
        return pre



相关文章
|
2天前
|
存储 Java
Java数据结构:链表
Java数据结构:链表
15 2
TU^
|
6天前
|
存储 索引
数据结构~~链表
链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的
TU^
16 0
|
1天前
|
缓存 算法
【数据结构】----链表--双向链表
【数据结构】----链表--双向链表
7 0
|
1天前
|
存储 缓存 算法
【数据结构】线性表----链表详解
【数据结构】线性表----链表详解
5 0
|
2天前
|
存储
数据结构——链表
数据结构——链表
10 0
|
2天前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
11 1
|
3天前
|
Java
DAY-1 | Java数据结构之链表:删除无头单链表中等于给定值 val 的所有节点
力扣203题解:使用时间复杂度为O(n)的思路删除链表中所有值为key的元素。引入辅助指针pre,记录cur的前一个节点,遍历链表时,若cur.val!=key,pre和cur同时前进;若cur.val==key,则pre.next=cur.next,cur继续前进,确保pre不急于跟随以处理连续相同值的情况。遍历结束后,处理头节点可能需要删除的特殊情况。
15 0
|
6天前
|
存储 缓存
数据结构(链表)
数据结构(链表)
14 0
|
7天前
|
算法 测试技术
【数据结构与算法 | 基础篇】单向循环链表实现队列
【数据结构与算法 | 基础篇】单向循环链表实现队列
|
7天前
|
算法 索引
【数据结构与算法 | 基础篇】[链表专题]力扣141, 142
【数据结构与算法 | 基础篇】[链表专题]力扣141, 142