04-1单向链表.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "元素3\t元素2\t元素1\t元素4\t元素5\t\n",
      "False\n",
      "元素3\t元素2\t元素4\t元素5\t\n",
      "元素3\t元素2\t元素4\t元素5\t元素6666\t\n",
      "5\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "class SingleNode(object):\n",
    "  # 单链表的结点”\n",
    "  def __init__(self,item):\n",
    "    # item存放数据元素\n",
    "    self.item = item\n",
    "    # next是下一个节点的标识\n",
    "    self.next = None\n",
    "\n",
    "class SingleLinkList:\n",
    "  def __init__(self):\n",
    "    self.__head: SingleNode  = None\n",
    "\n",
    "  # - is_empty() 链表是否为空\n",
    "  def is_empty(self):\n",
    "      return self.__head is None\n",
    "\n",
    "\n",
    "  # - Length() 链表长度\n",
    "  def length(self):\n",
    "      cur = self.__head\n",
    "      count = 0\n",
    "      while cur is not None:\n",
    "            cur = cur.next\n",
    "            count += 1\n",
    "      return count\n",
    "      \n",
    "\n",
    "  # - traveL() 遍历整个链表\n",
    "  def travel(self):\n",
    "    cur: SingleNode = self.__head\n",
    "    while cur is not None:\n",
    "      print(cur.item,end = \"\\t\")\n",
    "      cur = cur.next\n",
    "    print(\"\")\n",
    "\n",
    "\n",
    "\n",
    "  # - add(item) 链表头部添加元素\n",
    "  def add(self,item):\n",
    "    node = SingleNode(item)\n",
    "    node.next = self.__head\n",
    "    self.__head = node\n",
    "\n",
    "  # - append(item) 链表尾部添加元素\n",
    "  def append(self,item):\n",
    "    node = SingleNode(item)\n",
    "    # 如果最后结尾没有节点 新添加的直接指向该节点\n",
    "    if self.__head is None:\n",
    "      self.__head = node\n",
    "    # 如果有该节点\n",
    "    else:\n",
    "      # 遍历\n",
    "      cur = self.__head\n",
    "      while cur.next is not None:\n",
    "        cur = cur.next # 获取最后一个节点\n",
    "      cur.next = node\n",
    "\n",
    "  # - insert(pos，item) 指定位置添加元素\n",
    "  def insert(self,pos,item):\n",
    "        if pos <= 0 :    \n",
    "          self.add(item)\n",
    "        elif pos >= self.length():\n",
    "          self.append(item)\n",
    "        else:\n",
    "          cur = self.__head\n",
    "          count = 0\n",
    "          while count < (pos-1):\n",
    "                count += 1\n",
    "                cur = cur.next\n",
    "          # 等于要插入的位置 哦一个节点ya\n",
    "          node = SingleNode(item)\n",
    "          # 当前的下一个是插入node的下一个\n",
    "          node.next = cur.next\n",
    "          # 节点是当前的下一个\n",
    "          cur.next= node\n",
    "\n",
    "\n",
    "\n",
    "  # - remove(item) 删除节点\n",
    "  def remove(self,item):\n",
    "        cur: SingleNode = self.__head\n",
    "        pre = None\n",
    "        while cur is not None:\n",
    "            if cur.item == item:\n",
    "                # 在头部 直接覆盖掉\n",
    "                if cur == self.__head:\n",
    "                    self.__head = cur.next\n",
    "                else:\n",
    "                    pre.next = cur.next\n",
    "                return True\n",
    "            pre = cur # 记录一下上一个节点，开启下一个轮回\n",
    "            cur = cur.next\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "  # - search(item) 查找节点是否存在\n",
    "  def search(self,item):\n",
    "        cur: SingleNode = self.__head\n",
    "        while cur is not None:\n",
    "            if cur.item == item:\n",
    "                return True\n",
    "            cur = cur.next\n",
    "        return False\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "\n",
    "    single_link_list = SingleLinkList()\n",
    "    single_link_list.add(\"元素1\")\n",
    "    single_link_list.add(\"元素2\")\n",
    "    single_link_list.add(\"元素3\")\n",
    "    single_link_list.append(\"元素4\")\n",
    "    single_link_list.append(\"元素5\")\n",
    "    single_link_list.travel()\n",
    "    print(single_link_list.search(\"元素6\"))\n",
    "    single_link_list.remove(\"元素1\")\n",
    "    single_link_list.travel()\n",
    "    single_link_list.insert(12,\"元素6666\")\n",
    "    single_link_list.travel()\n",
    "    print(single_link_list.length())\n",
    "    print(single_link_list.is_empty())"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "pytorch3.7",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.11"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}