欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构之链表的实现

程序员文章站 2024-02-29 21:34:16
...

数据结构------链表

ps:假期闲到慌。。想着把学过的比较基础又实用的东西捋一捋也顺道复习一下吧
正文开始:
链表是一种线性的数据结构,链表的各个元素可以理解为一个节点,这个节点会有一个值,还会有一个引用字段将各个节点链接在一起(可以理解为一个指针指向下一个元素,即这个节点由两部分组成:值+指针),链表相较于数组在索引访问数据比较慢,但是在删除和插入方面很是方便,常见链表的分为单链表和双链表。

单链表

实现以下功能:

1.get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1;
2. addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点;
3. addAtTail(val):将值为 val 的节点追加到链表的最后一个元素;
4. addAtIndex(index,val):在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点;
5. deleteAtIndex(index):如果索引 index 有效,则删除链表中的第 index 个节点;
图示:
数据结构之链表的实现
代码如下:

class Node(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class MyLinkedList:

    def __init__(self):
        self.size = 0
        self.head = Node(0)

    def get(self, index: int) -> int:
        if index < 0: return -1
        node = self.head
        for _ in range(index + 1):
            if node.next is not None:
                node = node.next
            else:
                return -1
        return node.val

    def addAtHead(self, val: int) -> None:
        self.size += 1
        p = Node(val)
        p.next = self.head.next
        self.head.next = p

    def addAtTail(self, val: int) -> None:
        self.size += 1
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(val)

    def addAtIndex(self, index: int, val: int) -> None:
        self.size += 1
        cur = self.head
        for i in range(index):
            if cur.next is None:
                return
            cur = cur.next
        if cur is Node:
            cur = Node(val)
        else:
            new = Node(val)
            new.next = cur.next
            cur.next = new

    def deleteAtIndex(self, index: int) -> None:
        cur = self.head
        if index < 0: return
        for i in range(index):
            cur = cur.next
        if cur.next is not None:
            cur.next = cur.next.next
            self.size -= 1

测试如下:

obj = MyLinkedList()
obj.addAtHead(1)
obj.addAtTail(3)
obj.addAtIndex(1,2)  #链表变为1-> 2-> 3
print(obj.get(1))          #返回2
obj.deleteAtIndex(1)  #现在链表是1-> 3
print(obj.get(1))        #返回3
print(obj.head.next.val)
print(obj.head.next.next.val)  #链表的头节点一般为空
print(obj.size)

运行结果如下:
[图片]数据结构之链表的实现

双链表

图示:
数据结构之链表的实现
代码如下:

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

    def __init__(self):
        self.size = 0
        self.head = Node(0)
        self.tail = Node(0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, index: int) -> int:
        if index<0 or index>=self.size:
            return -1
        if index + 1 < self.size - index: #双向链表的话只要需要索引,这个地方可以选择最近的一边进行查找,仅对此函数操作一下
            node = self.head
            for i in range(index+1):         
                node = node.next
        else:
            node = self.tail
            for i in range(self.size - index):
                node = node.prev
        return node.val

    def addAtHead(self, val: int) -> None:
        one,two = self.head,self.head.next
        p = Node(val)
        p.next = two
        p.prev = one
        one.next = p
        two.prev = p
        self.size += 1


    def addAtTail(self, val: int) -> None:
        one,two = self.tail,self.tail.prev
        p = Node(val)
        p.next = one
        p.prev = two
        one.prev = p
        two.next = p
        self.size += 1


    def addAtIndex(self, index: int, val: int) -> None:
        
        if index > self.size:
            return 
        if index < 0:
            index = 0
        l = self.head
        for i in range(index):
            l = l.next
        r = l.next
        self.size += 1
        p = Node(val)
        p.next = r
        p.prev = l
        l.next = p
        r.prev = p

    def deleteAtIndex(self, index: int) -> None:
        if index >= self.size or index < 0:
            return 
        l = self.head
        for i in range(index):
            l = l.next
        r = l.next.next
        self.size -= 1
        l.next = r
        r.prev = l
     

听说这东西后面还可以改?那先这样以后有啥新点子再完善。。