数据结构之链表的实现

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

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
     

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