浅谈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()
Hot AI Tools
Undresser.AI Undress
AI-powered app for creating realistic nude photos
AI Clothes Remover
Online AI tool for removing clothes from photos.
Undress AI Tool
Undress images for free
Clothoff.io
AI clothes remover
AI Hentai Generator
Generate AI Hentai for free.
Hot Article
Hot Tools
Notepad++7.3.1
Easy-to-use and free code editor
SublimeText3 Chinese version
Chinese version, very easy to use
Zend Studio 13.0.1
Powerful PHP integrated development environment
Dreamweaver CS6
Visual web development tools
SublimeText3 Mac version
God-level code editing software (SublimeText3)
Hot Topics
Is the conversion speed fast when converting XML to PDF on mobile phone?
Apr 02, 2025 pm 10:09 PM
The speed of mobile XML to PDF depends on the following factors: the complexity of XML structure. Mobile hardware configuration conversion method (library, algorithm) code quality optimization methods (select efficient libraries, optimize algorithms, cache data, and utilize multi-threading). Overall, there is no absolute answer and it needs to be optimized according to the specific situation.
How to convert XML files to PDF on your phone?
Apr 02, 2025 pm 10:12 PM
It is impossible to complete XML to PDF conversion directly on your phone with a single application. It is necessary to use cloud services, which can be achieved through two steps: 1. Convert XML to PDF in the cloud, 2. Access or download the converted PDF file on the mobile phone.
What is the function of C language sum?
Apr 03, 2025 pm 02:21 PM
There is no built-in sum function in C language, so it needs to be written by yourself. Sum can be achieved by traversing the array and accumulating elements: Loop version: Sum is calculated using for loop and array length. Pointer version: Use pointers to point to array elements, and efficient summing is achieved through self-increment pointers. Dynamically allocate array version: Dynamically allocate arrays and manage memory yourself, ensuring that allocated memory is freed to prevent memory leaks.
Is there any mobile app that can convert XML into PDF?
Apr 02, 2025 pm 08:54 PM
An application that converts XML directly to PDF cannot be found because they are two fundamentally different formats. XML is used to store data, while PDF is used to display documents. To complete the transformation, you can use programming languages and libraries such as Python and ReportLab to parse XML data and generate PDF documents.
How to convert xml into pictures
Apr 03, 2025 am 07:39 AM
XML can be converted to images by using an XSLT converter or image library. XSLT Converter: Use an XSLT processor and stylesheet to convert XML to images. Image Library: Use libraries such as PIL or ImageMagick to create images from XML data, such as drawing shapes and text.
Recommended XML formatting tool
Apr 02, 2025 pm 09:03 PM
XML formatting tools can type code according to rules to improve readability and understanding. When selecting a tool, pay attention to customization capabilities, handling of special circumstances, performance and ease of use. Commonly used tool types include online tools, IDE plug-ins, and command-line tools.
What is the process of converting XML into images?
Apr 02, 2025 pm 08:24 PM
To convert XML images, you need to determine the XML data structure first, then select a suitable graphical library (such as Python's matplotlib) and method, select a visualization strategy based on the data structure, consider the data volume and image format, perform batch processing or use efficient libraries, and finally save it as PNG, JPEG, or SVG according to the needs.
Is there a mobile app that can convert XML into PDF?
Apr 02, 2025 pm 09:45 PM
There is no APP that can convert all XML files into PDFs because the XML structure is flexible and diverse. The core of XML to PDF is to convert the data structure into a page layout, which requires parsing XML and generating PDF. Common methods include parsing XML using Python libraries such as ElementTree and generating PDFs using ReportLab library. For complex XML, it may be necessary to use XSLT transformation structures. When optimizing performance, consider using multithreaded or multiprocesses and select the appropriate library.
