Python線性表種的單連結串列詳解

class Node():
"""
單連結串列中的節點應該具有兩個屬性：val 和 next。
val 是當前節點的值，
next 是指向下一個節點的指標/參照。
"""
def __init__(self, value):
# 存放元素資料
self.val = value
# next是下一個節點的標識
self.next = None

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
@Author : Young
@File : linked_list2.py
@version : 1.0
@Time : 2019/4/5 11:06
Description about this file:

"""
class Node():
"""
單連結串列中的節點應該具有兩個屬性：val 和 next。
val 是當前節點的值，
next 是指向下一個節點的指標/參照。
"""

def __init__(self, value):
# 存放元素資料
self.val = value
# next是下一個節點的標識
self.next = None


class SingleLinkList():
def __init__(self, node=None):
# 頭節點定義為私有變數
self._head = node

def is_empty(self):
# 判斷連結串列是否為空
if self._head is None:
return True
else:
return False

def get(self, index: int) -> int:
"""
獲取連結串列中第 index 個節點的值。如果索引無效，則返回-1
:param index: 索引值
:return:
"""
if self._head is None:
return -1
cur = self._head
for i in range(index):
if cur.next is None:
return -1
cur = cur.next
return cur.val

def length(self):
"""
cur遊標，用來移動遍歷節點
count用來計數
:return: 返回連結串列的長度
"""
cur = self._head
count = 0
while cur is not None:
count += 1
cur = cur.next
return count

def travel(self):
"""
遍歷整個連結串列
:return:
"""
cur = self._head
while cur is not None:
print(cur.elem, end=' ')
cur = cur.next

def add_at_head(self, val: int) -> None:
"""
在頭部新增一個節點
:param val:
:return: None
"""
# 先建立一個儲存item值的節點
node = Node(val)
# 判斷連結串列是否為空
if self._head is None:
self._head = node
else:
# 將新節點的連結域next指向頭節點，即_head指向的位置
node.next = self._head
# 將連結串列的頭_head指向新節點
self._head = node

def add_at_tail(self, val: int) -> None or int:
"""
在尾部新增一個節點
:param item:
:return:
"""
node = Node(val)
# 若連結串列為空，直接將該節點作為連結串列的第一個元素
if self._head is None:
self._head = node
else:
cur = self._head
while cur.next is not None:
cur = cur.next
cur.next = node

def add_at_index(self, index: int, val: int) -> None:
"""
在指定位置pos新增節點
pos從0開始
:param index:
:param val:
:return:
"""
# 若指定位置pos為第一個元素之前，則執行頭部插入
if index <= 0:
self.add_at_head(val)
# 若指定位置超過連結串列尾部，則執行尾部插入
elif index >= self.length():
self.add_at_tail(val)
# 找到指定位置
else:
# pre用來指向指定位置pos的前一個位置pos-1，初始從頭節點開始移動到指定位置
pre = self._head
count = 0
node = Node(val)
# 在目標節點的前一位停下
while count < (index - 1):
count += 1
pre = pre.next
# 先將新節點node的next指向插入位置的節點
node.next = pre.next
# 將插入位置的前一個節點的next指向新節點
pre.next = node

def delete_at_index(self, index: int) -> None or int:
"""
如果索引 index 有效，則刪除連結串列中的第 index 個節點。
:param index: 對應的索引值
:return: -1表示為異常
"""
pre = None
cur = self._head
if index is 0:
self._head = None
for i in range(index):
if cur.next is None:
# raise IndexError("越界")
return -1
pre = cur
cur = pre.next
else:
pre.next = cur.next

def search(self, val: int) -> True or False:
"""
查詢節點是否存在
:param val: 節點的val值
:return:
"""
cur = self._head
while cur is not None:
if cur.val == val:
return True
else:
cur = cur.next
return False

if __name__ == '__main__':
obj = SingleLinkList()
obj.add_at_head(1)
obj.add_at_tail(3)
obj.add_at_index(1, 2)
obj.travel()
obj.delete_at_index(1)
obj.travel()