浅谈Python单向链表的实现

链表由一系列不必在内存中相连的结构构成，这些对象按线性顺序排序。每个结构含有表元素和指向后继元素的指针。最后一个单元的指针指向NULL。为了方便链表的删除与插入操作，可以为链表添加一个表头。

删除操作可以通过修改一个指针来实现。

插入操作需要执行两次指针调整。

1. 单向链表的实现

1.1 Node实现

    每个Node分为两部分。一部分含有链表的元素，可以称为数据域；另一部分为一指针，指向下一个Node。

class Node():
  __slots__=['_item','_next']  #限定Node实例的属性
  def __init__(self,item):
    self._item=item
    self._next=None   #Node的指针部分默认指向None
  def getItem(self):
    return self._item
  def getNext(self):
    return self._next
  def setItem(self,newitem):
    self._item=newitem
  def setNext(self,newnext):
    self._next=newnext

1.2 SinglelinkedList的实现

class SingleLinkedList():
  def __init__(self):
    self._head=None  #初始化链表为空表
    self._size=0

1.3 检测链表是否为空

def isEmpty(self):
  return self._head==None

1.4 add在链表前端添加元素

def add(self,item):
  temp=Node(item)
  temp.setNext(self._head)
  self._head=temp

1.5 append在链表尾部添加元素

def append(self,item):
  temp=Node(item)
  if self.isEmpty():
    self._head=temp  #若为空表，将添加的元素设为第一个元素
  else:
    current=self._head
    while current.getNext()!=None:
      current=current.getNext()  #遍历链表
    current.setNext(temp)  #此时current为链表最后的元素

1.6 search检索元素是否在链表中

def search(self,item):
  current=self._head
  founditem=False
  while current!=None and not founditem:
    if current.getItem()==item:
      founditem=True
    else:
      current=current.getNext()
  return founditem

1.7 index索引元素在链表中的位置

def index(self,item):
  current=self._head
  count=0
  found=None
  while current!=None and not found:
    count+=1
    if current.getItem()==item:
      found=True
    else:
      current=current.getNext()
  if found:
    return count
  else:
    raise ValueError,'%s is not in linkedlist'%item

1.8 remove删除链表中的某项元素

def remove(self,item):
  current=self._head
  pre=None
  while current!=None:
    if current.getItem()==item:
      if not pre:
        self._head=current.getNext()
      else:
        pre.setNext(current.getNext())
      break
    else:
      pre=current
      current=current.getNext()

1.9 insert链表中插入元素

def insert(self,pos,item):
  if pos<=1:
    self.add(item)
  elif pos>self.size():
    self.append(item)
  else:
    temp=Node(item)
    count=1
    pre=None
    current=self._head
    while count<pos:
      count+=1
      pre=current
      current=current.getNext()
    pre.setNext(temp)
    temp.setNext(current)

全部代码

class Node():
  __slots__=['_item','_next']
  def __init__(self,item):
    self._item=item
    self._next=None
  def getItem(self):
    return self._item
  def getNext(self):
    return self._next
  def setItem(self,newitem):
    self._item=newitem
  def setNext(self,newnext):
    self._next=newnext

class SingleLinkedList():
  def __init__(self):
    self._head=None #初始化为空链表
  def isEmpty(self):
    return self._head==None
  def size(self):
    current=self._head
    count=0
    while current!=None:
      count+=1
      current=current.getNext()
    return count
  def travel(self):
    current=self._head
    while current!=None:
      print current.getItem()
      current=current.getNext()
  def add(self,item):
    temp=Node(item)
    temp.setNext(self._head)
    self._head=temp

  def append(self,item):
    temp=Node(item)
    if self.isEmpty():
      self._head=temp  #若为空表，将添加的元素设为第一个元素
    else:
      current=self._head
      while current.getNext()!=None:
        current=current.getNext()  #遍历链表
      current.setNext(temp)  #此时current为链表最后的元素
  def search(self,item):
    current=self._head
    founditem=False
    while current!=None and not founditem:
      if current.getItem()==item:
        founditem=True
      else:
        current=current.getNext()
    return founditem
  def index(self,item):
    current=self._head
    count=0
    found=None
    while current!=None and not found:
      count+=1
      if current.getItem()==item:
        found=True
      else:
        current=current.getNext()
    if found:
      return count
    else:
      raise ValueError,'%s is not in linkedlist'%item
  def remove(self,item):
    current=self._head
    pre=None
    while current!=None:
      if current.getItem()==item:
        if not pre:
          self._head=current.getNext()
        else:
          pre.setNext(current.getNext())
        break
      else:
        pre=current
        current=current.getNext()
  def insert(self,pos,item):
    if pos<=1:
      self.add(item)
    elif pos>self.size():
      self.append(item)
    else:
      temp=Node(item)
      count=1
      pre=None
      current=self._head
      while count<pos:
        count+=1
        pre=current
        current=current.getNext()
      pre.setNext(temp)
      temp.setNext(current)

if __name__=='__main__':
  a=SingleLinkedList()
  for i in range(1,10):
    a.append(i)
  print a.size()
  a.travel()
  print a.search(6)
  print a.index(5)
  a.remove(4)
  a.travel()
  a.insert(4,100)
  a.travel()

Kenyataan Laman Web ini

Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Alat AI Hot

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Penyingkiran pakaian AI

AI Hentai Generator

Menjana ai hentai secara percuma.

Tunjukkan Lagi

Artikel Panas

R.E.P.O. Kristal tenaga dijelaskan dan apa yang mereka lakukan (kristal kuning)

2 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌

Hello Kitty Island Adventure: Cara mendapatkan biji gergasi

1 bulan yang lalu By 尊渡假赌尊渡假赌尊渡假赌

Berapa lama masa yang diperlukan untuk mengalahkan fiksyen berpecah?

4 minggu yang lalu By DDD

R.E.P.O. Simpan Fail Lokasi: Di ​​manakah & bagaimana untuk melindunginya?

4 minggu yang lalu By DDD

Muzium Dua Point: Semua Pameran dan Di Mana Mencari Mereka

1 bulan yang lalu By 尊渡假赌尊渡假赌尊渡假赌

Tunjukkan Lagi

Alat panas

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Tunjukkan Lagi

Topik panas

Di manakah pintu masuk log masuk untuk e-mel gmail?

7378

15

Tutorial Java

1628

14

Tutorial CakePHP

1357

52

Tutorial Laravel

1267

25

Tutorial PHP

1216

29

Tunjukkan Lagi

Related knowledge

Adakah kelajuan penukaran cepat apabila menukar XML ke PDF pada telefon bimbit? Apr 02, 2025 pm 10:09 PM

Kelajuan XML mudah alih ke PDF bergantung kepada faktor -faktor berikut: kerumitan struktur XML. Kaedah Penukaran Konfigurasi Perkakasan Mudah Alih (Perpustakaan, Algoritma) Kaedah Pengoptimuman Kualiti Kod (Pilih perpustakaan yang cekap, mengoptimumkan algoritma, data cache, dan menggunakan pelbagai threading). Secara keseluruhannya, tidak ada jawapan mutlak dan ia perlu dioptimumkan mengikut keadaan tertentu.

Adakah terdapat aplikasi mudah alih yang boleh menukar XML ke PDF? Apr 02, 2025 pm 08:54 PM

Permohonan yang menukarkan XML terus ke PDF tidak dapat dijumpai kerana mereka adalah dua format yang berbeza. XML digunakan untuk menyimpan data, manakala PDF digunakan untuk memaparkan dokumen. Untuk melengkapkan transformasi, anda boleh menggunakan bahasa pengaturcaraan dan perpustakaan seperti Python dan ReportLab untuk menghuraikan data XML dan menghasilkan dokumen PDF.

Bagaimana cara menukar fail XML ke PDF di telefon anda? Apr 02, 2025 pm 10:12 PM

Tidak mustahil untuk menyelesaikan penukaran XML ke PDF secara langsung di telefon anda dengan satu aplikasi. Ia perlu menggunakan perkhidmatan awan, yang boleh dicapai melalui dua langkah: 1. Tukar XML ke PDF di awan, 2. Akses atau muat turun fail PDF yang ditukar pada telefon bimbit.

Apakah fungsi jumlah bahasa C? Apr 03, 2025 pm 02:21 PM

Tiada fungsi jumlah terbina dalam dalam bahasa C, jadi ia perlu ditulis sendiri. Jumlah boleh dicapai dengan melintasi unsur -unsur array dan terkumpul: Versi gelung: SUM dikira menggunakan panjang gelung dan panjang. Versi Pointer: Gunakan petunjuk untuk menunjuk kepada unsur-unsur array, dan penjumlahan yang cekap dicapai melalui penunjuk diri sendiri. Secara dinamik memperuntukkan versi Array: Perlawanan secara dinamik dan uruskan memori sendiri, memastikan memori yang diperuntukkan dibebaskan untuk mengelakkan kebocoran ingatan.

Bagaimana cara mengawal saiz XML ditukar kepada imej? Apr 02, 2025 pm 07:24 PM

Untuk menjana imej melalui XML, anda perlu menggunakan perpustakaan graf (seperti bantal dan JFreechart) sebagai jambatan untuk menjana imej berdasarkan metadata (saiz, warna) dalam XML. Kunci untuk mengawal saiz imej adalah untuk menyesuaikan nilai & lt; lebar & gt; dan & lt; ketinggian & gt; Tag dalam XML. Walau bagaimanapun, dalam aplikasi praktikal, kerumitan struktur XML, kehalusan lukisan graf, kelajuan penjanaan imej dan penggunaan memori, dan pemilihan format imej semuanya mempunyai kesan ke atas saiz imej yang dihasilkan. Oleh itu, perlu mempunyai pemahaman yang mendalam tentang struktur XML, mahir dalam perpustakaan grafik, dan mempertimbangkan faktor -faktor seperti algoritma pengoptimuman dan pemilihan format imej.

Cara menukar XML ke dalam gambar Apr 03, 2025 am 07:39 AM

XML boleh ditukar kepada imej dengan menggunakan perpustakaan penukar XSLT atau imej. XSLT Converter: Gunakan pemproses XSLT dan stylesheet untuk menukar XML ke imej. Perpustakaan Imej: Gunakan perpustakaan seperti PIL atau ImageMagick untuk membuat imej dari data XML, seperti bentuk lukisan dan teks.

Cara Membuka Format XML Apr 02, 2025 pm 09:00 PM

Gunakan kebanyakan editor teks untuk membuka fail XML; Jika anda memerlukan paparan pokok yang lebih intuitif, anda boleh menggunakan editor XML, seperti editor XML oksigen atau XMLSPY; Jika anda memproses data XML dalam program, anda perlu menggunakan bahasa pengaturcaraan (seperti Python) dan perpustakaan XML (seperti XML.Etree.ElementTree) untuk menghuraikan.

Alat pemformatan XML yang disyorkan Apr 02, 2025 pm 09:03 PM

Alat pemformatan XML boleh menaip kod mengikut peraturan untuk meningkatkan kebolehbacaan dan pemahaman. Apabila memilih alat, perhatikan keupayaan penyesuaian, pengendalian keadaan khas, prestasi dan kemudahan penggunaan. Jenis alat yang biasa digunakan termasuk alat dalam talian, pemalam IDE, dan alat baris arahan.

See all articles