链表增加结点

有三种情况：

1. add(item)链表头部增加结点
2. append(item)尾部增加结点
3. insert(pos, item)指定位置增加结点

add(item)链表头部增加结点

步骤

• 新结点的next指向原始的头结点 new_node.next = head
• 然后让head指向新结点 head = new_node

# 单链表的实现
class SingleLinkList(object):
   ......
    # 头部增加结点
    # add()
    def add(self, item):
        # 新结点存储新数据
        node = SingleNode(item)
        node.next = self.head
        self.head = node

append(item)尾部增加结点

步骤

尾结点.next = 新结点

如何找到尾结点：

cur = head
while cur.next is not None:
	cur = cur.next

# 单链表的实现
class SingleLinkList(object):
    def __init__(self, node=None):
        # head: 首结点
        self.head = node
    # 判断链表是否为空
    def is_empty(self):
        if self.head is None:
            return True
        else:
            return False
    # 获取链表长度
    ......
    # 遍历链表
    ......

    # 头部增加结点
    ......

    # 尾部增加结点
    # append()
    def append(self, item):
        # 新结点存储数据
        node = SingleNode(item)

        # 判断是否为空链表
        if self.is_empty():
            self.head = node
        else:
            cur = self.head
            # 找到尾结点
            while cur.next is not None:
                cur = cur.next

            cur.next = node

在指定位置增加结点

• 在pos -1, 与 pos之间新增结点，需要注意
  • 如果pos为0即负数，那么就直接在头部新增结点
  • 如果pos大于等于链表长度，则直接在尾部新增结点

# 单链表的实现
class SingleLinkList(object):
    def __init__(self, node=None):
        # head: 首结点
        self.head = node
    # 判断链表是否为空
    def is_empty(self):
        if self.head is None:
            return True
        else:
            return False
    # 获取链表长度
    def length(self):
        # 游标记录当前所在的位置
        cur = self.head
        # 记录链表的长度
        count = 0

        while cur is not None:
            cur = cur.next
            count += 1

        return count
    # 遍历链表
    ......

    # 头部增加结点
    # add()
    ......

    # 尾部增加结点
    # append()
    ......

    # 指定位置增加结点
    # insert(pos, item)
    def insert(self, pos, item):
        # 头部增加新结点
        if pos <= 0:
            self.add(item)
        elif pos >= self.length():
            # 尾部添加结点
            self.append(item)
        else:
            # 游标
            cur = self.head
            # 计数
            count = 0
            # 新结点
            node = SingleNode(item)

            # 找到插入位置的前一个结点
            while count < pos - 1:
                cur = cur.next
                count += 1

            # 完成插入新结点
            node.next = cur.next
            cur.next = node