# !/usr/bin/env python
# -*- coding: utf-8 -*-
 
__author__ = 'MrHero'
 
 
class Node(object):
  """
  線性表的存儲結構
  和 C 語言中的鏈式存儲結構類似
  """
  def __init__(self, data=None):
    self.data = data
    self.next = None
 
 
class LKList(object):
  """
  線性表的具體操作
  """
 
  def __init__(self):
    """
    相當于初始化線性表, 即創(chuàng)建頭結點
    頭節(jié)點為空節(jié)點，占據位置號為0
    創(chuàng)建好的表即為: 頭節(jié)點[0]->節(jié)點[1]->節(jié)點[2]->節(jié)點[3]->節(jié)點[4]
    :return:
    """
    self.L = Node(None)
    self.L.next = None
    self.length = 0
 
  def is_empty(self):
    """
    判斷線新表的長度
    :return:
    """
    return self.length == 0
 
  def get_length(self):
    """
    獲取線新表的長度
    :return:
    """
    return self.length
 
  def insert(self, i, elem):
    """
    在指定位i處置插入元素elem
    :param i: 指定的位置
    :param elem: 插入的元素elem
    :return:
    """
    j = 0
    p = self.L
    while j < i-1 and p is not None: # 查找第 i-1 個節(jié)點
      j += 1
      p = p.next
    if p is None:  # 未找到邏輯位序為 i-1 的節(jié)點
      raise IndexError("Index is out of range!")
    else:  # 找到邏輯位序為 i-1 的節(jié)點
      tmp = Node(elem)
      tmp.next = p.next
      p.next = tmp
      self.length += 1
 
  def delete(self, i):
    """
    刪除指定節(jié)點的元素
    :param i: 指定節(jié)點
    :return: 刪除的指定節(jié)點元素值
    """
    if self.is_empty():
      raise IndexError("The list is empty!")
    elif 0 < i <= self.length:
      j = 1
      p = self.L
      while j < i and p:
        p = p.next
        j += 1
      delelte_node = p.next
      p.next = delelte_node.next
      self.length -= 1
      return delelte_node.data
    else:
      raise IndexError("Index is out of range!")
 
  def get_elem(self, i):
    """
    獲取某個節(jié)點的值
    :param i:
    :return:返回某個節(jié)點的值
    """
    if self.is_empty():
      raise IndexError("The list is empty")
    elif 0 < i <= self.length:
      j = 0
      p = self.L
      while j < i and p:
        p = p.next
        j += 1
      print p.data
    else:
      raise IndexError("Index is out of range!")
 
  def locate_elem(self, elem):
    """
    查找某值的位置
    :param elem:
    :return: 返回第一個值等于elem的位置
    """
    j = 0
    p = self.L
    while p is not None and p.data != elem:
      p = p.next
      j += 1
    if p is Node:
      return -1
    else:
      return j
 
  def create_dict_list_H(self, list):
    """
    頭插法建表
    :param list:
    :return:
    """
    p = self.L
    for i in range(len(list)):
      tmp = Node(list[i])
      tmp.next = p.next
      p.next = tmp
      self.length += 1
 
  def create_dict_list_E(self, list):
    """
    尾插法建表
    :param list:
    :return:
    """
    p = self.L
    r = p
    for i in range(len(list)):
      tmp = Node(list[i])
      r.next = tmp
      r = tmp
      self.length += 1
    r.next = None
 
  def show_lklist(self):
    if self.is_empty():
      raise IndexError("It's a empty list!")
    else:
      j = 1
      p = self.L
      while j <= self.length and p:
        p = p.next
        if p is not None:
          print p.data
        j += 1
 
 
if __name__ == '__main__':
  lk = LKList()
  #
  # lk.create_dict_list_E([1, 2, 3, 4])
  # print "-----"
  # lk.get_elem(1)
  # lk.get_elem(2)
  # lk.get_elem(3)
  # lk.get_elem(4)
  # print "-------"
  # lk.show_lklist()
  # lk.insert(3, 5)
  # print "-------"
  # lk.show_lklist()
  # lo = lk.locate_elem(5)
  # print "location is %d" % lo
  # lk.delete(4)
  # print "-------"
  # lk.show_lklist()