# 創(chuàng)建節(jié)點(diǎn)
class Node(object):
  def __init__(self,item):
    self.element = item
    self.next = None
# 創(chuàng)建單鏈表類
class SingleLinkList(object):
  def __init__(self):
    self.header = None
    self.length = 0
  # 1、判斷是否為空
  def is_empty(self):
    if self.header == None:
      return True
    else:
      return False
  # 2、頭部插入
  def add(self,node):
    if self.is_empty():
      self.header = node
    else:
      node.next = self.header
      self.header = node
      # currentNode = self.header
    self.length += 1
  # 3、尾部插入
  def appent(self,node):
    currentNode = self.header
    if self.is_empty():
      self.add(node)
    else:
      while (currentNode.next != None):
        currentNode = currentNode.next
      currentNode.next = node
      self.length += 1
  # 4、指定位置插入
  def insert(self,node,index):
    currentNode = self.header
    if index>self.length+1 or index<=0:
      print("你要插入的位置不對，請重現(xiàn)選擇位置")
    if index == 1:
      self.add(node)
    elif index == 2:
      node.next = self.header.next
      self.header.next = node
      self.length += 1
    else:
      for i in range(1,index-1):
        currentNode = currentNode.next
      node.next = currentNode.next
      currentNode.next = node
      self.length += 1
  # 5、遍歷
  def travel(self):
    currentNode = self.header
    if self.length == 0:
      print("你要遍歷的鏈表沒有數(shù)據(jù)\n")
    else:
      print("你要遍歷的鏈表里面的元素有:",end=" ")
      for i in range(self.length):
        print("%s "%currentNode.element,end=" ")
        currentNode = currentNode.next
      print("\n")
  # 6、排序不用交換節(jié)點(diǎn)的位置，只需要交換節(jié)點(diǎn)上的數(shù)據(jù)值
  def list_sort(self):
    for i in range(0,self.length-1):
      currentNode = self.header
      for j in range(0,self.length-i-1):
        if currentNode.element > currentNode.next.element:
          temp = currentNode.element
          currentNode.element = currentNode.next.element
          currentNode.next.element = temp
        currentNode = currentNode.next
  # 7、按索引刪除
  def remove(self,index):
    if index<=0 or index>self.length:
      print("你輸入的下標(biāo)不對，請重新輸入")
      return
    else:
      if index == 1:
        self.header = self.header.next
        currentNode = self.header
      elif index == 2:
        currentNode = self.header
        currentNode.next = currentNode.next.next
      else:
        currentNode = self.header
        for i in range(1,index-1):
          currentNode = currentNode.next
        currentNode.next = currentNode.next.next
    self.length -= 1
  # 8、查找是否包含,并返回下標(biāo)
  def isContain(self,num):
    contain = 0
    currentNode = self.header
    for i in range(self.length):
      if currentNode.element == num:
        print("%d在鏈表中%d處\n"%(num,i))
        contain = 1
      currentNode = currentNode.next
    if contain == 0:
      print("%d不在鏈表中\(zhòng)n"%num)
  # 9、根據(jù)下標(biāo)找節(jié)點(diǎn)
  def searchNodeByIndex(self,index):
    currentNode = self.header
    if index<=0 or index>self.length:
      print("你輸入的下標(biāo)不對，請重新輸入\n")
      return 0
    else:
      for i in range(index-1):
        currentNode = currentNode.next
      return currentNode
  # 10、根據(jù)下標(biāo)修改節(jié)點(diǎn)的值
  def modifyByIndex(self,index,num):
    currentNode = self.header
    if index<=0 or index>self.length:
      print("你輸入的下標(biāo)不對，請重新輸入\n")
    else:
      for i in range(index-1):
        currentNode = currentNode.next
      currentNode.element = num
def main():
  # 創(chuàng)建一個(gè)節(jié)點(diǎn)對象
  node1 = Node(1)
  # 創(chuàng)建一個(gè)單鏈表對象
  single_link_list = SingleLinkList()
  print("驗(yàn)證空鏈表的遍歷")
  single_link_list.travel()
  print("驗(yàn)證頭插")
  single_link_list.add(node1)
  single_link_list.travel()
  print("驗(yàn)證尾插")
  node2 = Node(2)
  single_link_list.appent(node2)
  single_link_list.travel()
  print("驗(yàn)證按位置插入")
  node3 = Node(3)
  single_link_list.insert(node3,1)
  single_link_list.travel()
  print("繼續(xù)驗(yàn)證頭插")
  node4 = Node(5)
  single_link_list.add(node4)
  single_link_list.travel()
  print("繼續(xù)驗(yàn)證按位置插入")
  node5 = Node(4)
  single_link_list.insert(node5,4)
  single_link_list.travel()
  print("驗(yàn)證刪除")
  single_link_list.remove(3)
  single_link_list.travel()
  print("驗(yàn)證查找一個(gè)節(jié)點(diǎn)是否在鏈表中")
  single_link_list.isContain(8)
  print("驗(yàn)證按下標(biāo)查找節(jié)點(diǎn)")
  node = single_link_list.searchNodeByIndex(2)
  print("第二個(gè)節(jié)點(diǎn)的值為：%s"%node.element)
  print("\n驗(yàn)證排序")
  single_link_list.list_sort()
  single_link_list.travel()
  print("驗(yàn)證修改")
  single_link_list.modifyByIndex(2,10)
  single_link_list.travel()
if __name__ == '__main__':
  main()

#include <stdio.h>
typedef struct N
{
  int element;
  struct N *next;
}Node;
// 1、創(chuàng)建節(jié)點(diǎn)
Node *createNode(int num)
{
  Node *node;
  node = (Node *)malloc(sizeof(Node));
  node->element = num;
  node->next = NULL;
  return node;
}
// 2、創(chuàng)建鏈表
Node *createSingleLinkList(Node *node)
{
  Node *head = node;
  return head;
}
// 3、獲取鏈表長度
int getlength(Node *head)
{
  if (head == NULL)
  {
    return 0;
  }
  int count = 1;
  Node *current = head;
  while (current->next != NULL)
  {
    count++;
    current = current->next;
  }
  return count;
}
// 4、頭部插入
Node * add(Node *head, Node *node)
{
  if(head == NULL)
  {
    head = node;
    return head;
  }
  else
  {
    node->next = head;
    head = node;
    return head;
  }
}
// 5、尾部插入
Node * append(Node *head,Node *node)
{
  Node *current = head;
  if (current->next == NULL)
  {
    add(head, node);
  }
  else
  {
    int len = getlength(head);
    for (int i = 0; i<len-1; i++)
    {
      current = current->next;
    }
    current->next = node;
  }
  return head;
}
// 6、按下標(biāo)插入節(jié)點(diǎn)
Node * insert(Node *head,Node *node,int index)
{
  int len = getlength(head);
  if (index<=0||index>len+1)
  {
    printf("你要插入的位置不對，請重現(xiàn)選擇位置");
  }
  Node *current = head;
  if (index == 1)
  {
    head = add(head, node);
  }
  else if (index == 2)
  {
    node->next = head->next;
    head->next = node;
  }
  else
  {
    for (int i = 1; i<index-1; i++)
    {
      current = current->next;
    }
    node->next = current->next;
    current->next = node;
  }
  return head;
}
// 7、遍歷
void travel(Node *head)
{
  int len = getlength(head);
  printf("len = %d\n",len);
  Node *current = head;
  if (len == 0)
  {
    printf("你要遍歷的鏈表沒有數(shù)據(jù)\n");
  }
  else
  {
    printf("你要遍歷的鏈表里面的元素有: ");
    for (int i = 0; i<len; i++)
    {
      printf("%d ",current->element);
      current = current->next;
    }
    printf("\n");
  }
}
// 8、根據(jù)索引刪除
Node * delect(Node *head,int index)
{
  int len = getlength(head);
  if (index<=0||index>len)
  {
    printf("你輸入的下標(biāo)不對，請重新輸入");
    return head;
  }
  else
  {
    if (index == 1)
    {
      head = head->next;
    }
    else if (index == 2)
    {
      head->next = head->next->next;
    }
    else
    {
      Node *current = head;
      for (int i = 1; i<index-1; i++)
      {
        current = current->next;
      }
      current->next = current->next->next;
    }
  }
  return head;
}
// 9、查找是否包含，并返回下標(biāo)
void isContain(Node *head,int num)
{
  int contain = 0;
  Node *current = head;
  int len = getlength(head);
  for (int i = 0; i<len; i++)
  {
    if (current->element == num)
    {
      printf("%d在鏈表中的%d處\n",num,i+1);
      contain = 1;
    }
    current = current->next;
  }
  if (contain == 0)
  {
     printf("%d不在鏈表中\(zhòng)n",num);
  }
}
// 10、根據(jù)下標(biāo)找節(jié)點(diǎn)
Node *searchByIndex(Node *head , int index)
{
  int len = getlength(head);
  Node *current = head;
  if (index<=0||index>len)
  {
    printf("你輸入的下標(biāo)不對，請重新輸入");
    return head;
  }
  else
  {
    for (int i = 0; i<index-1; i++)
    {
      current = current->next;
    }
    return current;
  }
}
// 11、根據(jù)下標(biāo)修改節(jié)點(diǎn)的值
void modifyByIndex(Node *head,int index,int num)
{
  int len = getlength(head);
  Node *current = head;
  if (index<=0||index>len)
  {
    printf("你輸入的下標(biāo)不對，請重新輸入");
  }
  else
  {
    for (int i = 0; i<index-1; i++)
    {
      current = current->next;
    }
    current->element = num;
  }
}
int main(int argc, const char * argv[])
{
  printf("==========1、創(chuàng)建節(jié)點(diǎn)==========\n");
  Node * node1 = createNode(1);
  printf("==========2、創(chuàng)建單鏈表==========\n");
  Node * head = createSingleLinkList(node1);
  travel(head);
  printf("==========3、驗(yàn)證頭插==========\n");
  Node *node2 = createNode(0);
  head = add(head, node2);
  travel(head);
  Node *node3 = createNode(2);
  head = add(head, node3);
  travel(head);
  printf("==========4、驗(yàn)證尾插==========\n");
  Node *node4 = createNode(4);
  head = append(head,node4);
  travel(head);
  Node *node5 = createNode(5);
  head = append(head,node5);
  travel(head);
  printf("==========5、驗(yàn)證按下標(biāo)插入==========\n");
  Node *node6 = createNode(6);
  head = insert(head, node6, 1);
  travel(head);
  printf("==========6、驗(yàn)證按下標(biāo)刪除==========\n");
  head = delect(head, 2);
  travel(head);
  printf("==========7、驗(yàn)證是否包含==========\n");
  isContain(head, 8);
  printf("==========8、驗(yàn)證根據(jù)下標(biāo)找節(jié)點(diǎn)==========\n");
  Node *n = searchByIndex(head, 1);
  printf("第一個(gè)節(jié)點(diǎn)是%d\n",n->element);
  printf("==========9、驗(yàn)證根據(jù)下標(biāo)修改==========\n");
  modifyByIndex
(head, 3, 9);
    travel(head);
    return 0;
}