# LeetCode: 707. 设计链表¶

## 1、题目描述¶

• get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
• addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。
• deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
示例：



• 所有值都在 [1, 1000] 之内。
• 操作次数将在 [1, 1000] 之内。

## 2、解题思路¶

class Node:
def __init__(self, value, forward, previous):
self.value = value
self.forward = forward
self.previous = previous

def __init__(self):
"""
"""
self.tail = None
self.length = 0

def get(self, index: int) -> int:
"""
Get the value of the index-th node in the linked list. If the index is invalid, return -1.
"""
if (not self.length) or (index < 0) or (index + 1 > self.length):
return -1

back_length = self.length - index

count = 0
if back_length < index:
temp = self.tail
while count < back_length - 1:
temp = temp.previous
count += 1
return temp.value
else:
while count < index:
temp = temp.forward
count += 1

return temp.value

"""
Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
"""

node = Node(val, None, None)
else:

if not self.tail:
self.tail = node

self.length += 1

def addAtTail(self, val: int) -> None:
"""
Append a node of value val to the last element of the linked list.
"""

node = Node(val, None, None)
if not self.tail:
self.tail = node
else:
self.tail.forward = node
node.previous = self.tail
self.tail = node

self.length += 1

def addAtIndex(self, index: int, val: int) -> None:
"""
Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
"""
if index > self.length:
return

if index == 0 or index == -1:
return

if index == self.length:
return

back_length = self.length - index
node = Node(val, None, None)
count = 0
if back_length < index:
temp = self.tail
while count < back_length - 1:
temp = temp.previous
count += 1
else:
while count < index:
temp = temp.forward
count += 1
temp.previous.forward = node
node.previous = temp.previous
node.forward = temp
temp.previous = node

self.length += 1

def deleteAtIndex(self, index: int) -> None:
"""
Delete the index-th node in the linked list, if the index is valid.
"""
if not self.length or index < 0 or index + 1 > self.length:
return

if self.length == 1:
self.tail = None
self.length -= 1
return
if index == 0:
self.length -= 1
return
if index == self.length - 1:
self.tail = self.tail.previous
self.tail.forward = None
self.length -= 1
return

count = 0
back_length = self.length - index
if back_length < index:
temp = self.tail
while count < back_length - 1:
temp = temp.previous
count += 1
else:
while count < index:
temp = temp.forward
count += 1
temp.previous.forward = temp.forward
temp.forward.previous = temp.previous
self.length -= 1