Detailed introduction to the linked list of python data structure

This article mainly introduces the relevant information of the Python data structure linked list in detail, which has certain reference value. Interested friends can refer to it

Data structure is a must master in computer science As a subject, many previous textbooks used C language to implement linked lists. Because C has pointers, it can easily control memory and implement linked lists. Other languages ​​are not so convenient. Many use simulated linked lists. , but this time, I did not use a simulated linked list to implement it, because Python is a dynamic language and can directly assign objects to new variables.

Okay, before I talk about my implementation in python, let me briefly talk about the linked list. When we store a large wave of data, we often use arrays, but it is very troublesome when we perform insertion operations. Look at the example below. There is a bunch of data 1, 2, 3, 5, 6, 7. We want to insert it into 3 Insert 4 between 5 and 5. What will we do if we use an array? Of course, the data after 5 is moved back one position, and then 4 is inserted. This is very troublesome, but if I use a linked list, I can just insert 4 directly between 3 and 5, which sounds very convenient.

So what is the structure of the linked list? As the name suggests, a linked list is of course like a chain, with nodes connected together to form a data chain.

The node structure of the linked list is as follows:

data is the customized data, and next is the address of the next node.

The structure of the linked list is, head saves the address of the first node:

Next we will use python to implement the linked list

Python implements linked list

First, define the node class Node:

class Node:
  '''
  data: 节点保存的数据
  _next: 保存下一个节点对象
  '''
  def __init__(self, data, pnext=None):
    self.data = data
    self._next = pnext

  def __repr__(self):
    '''
    用来定义Node的字符输出，
    print为输出data
    '''
    return str(self.data)

Then, define the linked list class:

The linked list must include :

Attributes:

Linked list header: head

Linked list length: length

Method:

Judge whether it is empty: isEmpty( )

def isEmpty(self):
  return (self.length == 0

Add a node (add at the end of the linked list): append()

def append(self, dataOrNode):
  item = None
  if isinstance(dataOrNode, Node):
    item = dataOrNode
  else:
    item = Node(dataOrNode)

  if not self.head:
    self.head = item
    self.length += 1

  else:
    node = self.head
    while node._next:
      node = node._next
    node._next = item
    self.length += 1

Delete a node: delete()

#删除一个节点之后记得要把链表长度减一
def delete(self, index):
  if self.isEmpty():
    print "this chain table is empty."
    return

  if index < 0 or index >= self.length:
    print &#39;error: out of index&#39;
    return
  #要注意删除第一个节点的情况
  #如果有空的头节点就不用这样
  #但是我不喜欢弄头节点
  if index == 0:
    self.head = self.head._next
    self.length -= 1
    return

  #prev为保存前导节点
  #node为保存当前节点
  #当j与index相等时就
  #相当于找到要删除的节点
  j = 0
  node = self.head
  prev = self.head
  while node._next and j < index:
    prev = node
    node = node._next
    j += 1

  if j == index:
    prev._next = node._next
    self.length -= 1

Modify a node: update()

def update(self, index, data):
  if self.isEmpty() or index < 0 or index >= self.length:
    print &#39;error: out of index&#39;
    return
  j = 0
  node = self.head
  while node._next and j < index:
    node = node._next
    j += 1

  if j == index:
    node.data = data

Find a node: getItem()

def getItem(self, index):
  if self.isEmpty() or index < 0 or index >= self.length:
    print "error: out of index"
    return
  j = 0
  node = self.head
  while node._next and j < index:
    node = node._next
    j += 1

  return node.data

Find the index of a node: getIndex()

def getIndex(self, data):
  j = 0
  if self.isEmpty():
    print "this chain table is empty"
    return
  node = self.head
  while node:
    if node.data == data:
      return j
    node = node._next
    j += 1

  if j == self.length:
    print "%s not found" % str(data)
    return

Insert a node: insert()

def insert(self, index, dataOrNode):
  if self.isEmpty():
    print "this chain tabale is empty"
    return

  if index < 0 or index >= self.length:
    print "error: out of index"
    return

  item = None
  if isinstance(dataOrNode, Node):
    item = dataOrNode
  else:
    item = Node(dataOrNode)

  if index == 0:
    item._next = self.head
    self.head = item
    self.length += 1
    return

  j = 0
  node = self.head
  prev = self.head
  while node._next and j < index:
    prev = node
    node = node._next
    j += 1

  if j == index:
    item._next = node
    prev._next = item
    self.length += 1

Clear the linked list: clear()

def clear(self):
  self.head = None
  self.length = 0

The above is the method to be implemented in the linked list class.

Result of execution:

#The following is the complete code:

# -*- coding:utf8 -*-
#/usr/bin/env python

class Node(object):
 def __init__(self, data, pnext = None):
  self.data = data
  self._next = pnext

 def __repr__(self):
  return str(self.data)

class ChainTable(object):
 def __init__(self):
  self.head = None
  self.length = 0

 def isEmpty(self):
  return (self.length == 0)

 def append(self, dataOrNode):
  item = None
  if isinstance(dataOrNode, Node):
   item = dataOrNode
  else:
   item = Node(dataOrNode)

  if not self.head:
   self.head = item
   self.length += 1

  else:
   node = self.head
   while node._next:
    node = node._next
   node._next = item
   self.length += 1

 def delete(self, index):
  if self.isEmpty():
   print "this chain table is empty."
   return

  if index < 0 or index >= self.length:
   print &#39;error: out of index&#39;
   return

  if index == 0:
   self.head = self.head._next
   self.length -= 1
   return

  j = 0
  node = self.head
  prev = self.head
  while node._next and j < index:
   prev = node
   node = node._next
   j += 1

  if j == index:
   prev._next = node._next
   self.length -= 1

 def insert(self, index, dataOrNode):
  if self.isEmpty():
   print "this chain tabale is empty"
   return

  if index < 0 or index >= self.length:
   print "error: out of index"
   return

  item = None
  if isinstance(dataOrNode, Node):
   item = dataOrNode
  else:
   item = Node(dataOrNode)

  if index == 0:
   item._next = self.head
   self.head = item
   self.length += 1
   return

  j = 0
  node = self.head
  prev = self.head
  while node._next and j < index:
   prev = node
   node = node._next
   j += 1

  if j == index:
   item._next = node
   prev._next = item
   self.length += 1

 def update(self, index, data):
  if self.isEmpty() or index < 0 or index >= self.length:
   print &#39;error: out of index&#39;
   return
  j = 0
  node = self.head
  while node._next and j < index:
   node = node._next
   j += 1

  if j == index:
   node.data = data

 def getItem(self, index):
  if self.isEmpty() or index < 0 or index >= self.length:
   print "error: out of index"
   return
  j = 0
  node = self.head
  while node._next and j < index:
   node = node._next
   j += 1

  return node.data


 def getIndex(self, data):
  j = 0
  if self.isEmpty():
   print "this chain table is empty"
   return
  node = self.head
  while node:
   if node.data == data:
    return j
   node = node._next
   j += 1

  if j == self.length:
   print "%s not found" % str(data)
   return

 def clear(self):
  self.head = None
  self.length = 0

 def __repr__(self):
  if self.isEmpty():
   return "empty chain table"
  node = self.head
  nlist = &#39;&#39;
  while node:
   nlist += str(node.data) + &#39; &#39;
   node = node._next
  return nlist

 def __getitem__(self, ind):
  if self.isEmpty() or ind < 0 or ind >= self.length:
   print "error: out of index"
   return
  return self.getItem(ind)

 def __setitem__(self, ind, val):
  if self.isEmpty() or ind < 0 or ind >= self.length:
   print "error: out of index"
   return
  self.update(ind, val)

 def __len__(self):
  return self.length

The above is the detailed content of Detailed introduction to the linked list of python data structure. For more information, please follow other related articles on the PHP Chinese website!