浅谈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()

본 웹사이트의 성명

본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

핫 AI 도구

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

AI 옷 제거제

AI Hentai Generator

AI Hentai를 무료로 생성하십시오.

더보기

인기 기사

R.E.P.O. 에너지 결정과 그들이하는 일 (노란색 크리스탈)

3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌

R.E.P.O. 최고의 그래픽 설정

3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌

어 ass 신 크리드 그림자 : 조개 수수께끼 솔루션

1 몇 주 전 By DDD

R.E.P.O. 아무도들을 수없는 경우 오디오를 수정하는 방법

3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌

Atomfall에서 크레인 제어 키 카드를 찾을 수 있습니다

1 몇 주 전 By DDD

더보기

뜨거운 도구

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

더보기

뜨거운 주제

Gmail 이메일의 로그인 입구는 어디에 있나요?

7439

15

Cakephp 튜토리얼

1369

52

Steam의 계정 이름 형식은 무엇입니까?

76

11

Win11 활성화 키 영구

32

19

더보기

Related knowledge

C 언어 합계의 기능은 무엇입니까? Apr 03, 2025 pm 02:21 PM

C 언어에는 내장 합계 기능이 없으므로 직접 작성해야합니다. 합계는 배열 및 축적 요소를 가로 질러 달성 할 수 있습니다. 루프 버전 : 루프 및 배열 길이를 사용하여 계산됩니다. 포인터 버전 : 포인터를 사용하여 배열 요소를 가리키며 효율적인 합계는 자체 증가 포인터를 통해 달성됩니다. 동적으로 배열 버전을 할당 : 배열을 동적으로 할당하고 메모리를 직접 관리하여 메모리 누출을 방지하기 위해 할당 된 메모리가 해제되도록합니다.

별개의 구별이 관련되어 있습니까? Apr 03, 2025 pm 10:30 PM

구별되고 구별되는 것은 구별과 관련이 있지만, 다르게 사용됩니다. 뚜렷한 (형용사)는 사물 자체의 독창성을 묘사하고 사물 사이의 차이를 강조하는 데 사용됩니다. 뚜렷한 (동사)는 구별 행동이나 능력을 나타내며 차별 과정을 설명하는 데 사용됩니다. 프로그래밍에서 구별은 종종 중복 제거 작업과 같은 컬렉션에서 요소의 독창성을 나타내는 데 사용됩니다. 홀수 및 짝수 숫자를 구별하는 것과 같은 알고리즘이나 함수의 설계에 별개가 반영됩니다. 최적화 할 때 별도의 작업은 적절한 알고리즘 및 데이터 구조를 선택해야하며, 고유 한 작업은 논리 효율성의 구별을 최적화하고 명확하고 읽을 수있는 코드 작성에주의를 기울여야합니다.

누가 더 많은 파이썬이나 자바 스크립트를 지불합니까? Apr 04, 2025 am 12:09 AM

기술 및 산업 요구에 따라 Python 및 JavaScript 개발자에 대한 절대 급여는 없습니다. 1. 파이썬은 데이터 과학 및 기계 학습에서 더 많은 비용을 지불 할 수 있습니다. 2. JavaScript는 프론트 엔드 및 풀 스택 개발에 큰 수요가 있으며 급여도 상당합니다. 3. 영향 요인에는 경험, 지리적 위치, 회사 규모 및 특정 기술이 포함됩니다.

이해하는 방법! x는? Apr 03, 2025 pm 02:33 PM

! x 이해! x는 C 언어로 된 논리적 비 운영자입니다. 그것은 x의 값, 즉 실제 변경, 거짓, 잘못된 변경 사항을 부수합니다. 그러나 C의 진실과 거짓은 부울 유형보다는 숫자 값으로 표시되며, 0이 아닌 것은 참으로 간주되며 0만이 거짓으로 간주됩니다. 따라서! x는 음수를 양수와 동일하게 처리하며 사실로 간주됩니다.

C 언어에서 합계는 무엇을 의미합니까? Apr 03, 2025 pm 02:36 PM

합에 대한 C에는 내장 합계 기능이 없지만 다음과 같이 구현할 수 있습니다. 루프를 사용하여 요소를 하나씩 축적합니다. 포인터를 사용하여 요소를 하나씩 액세스하고 축적합니다. 큰 데이터 볼륨의 경우 병렬 계산을 고려하십시오.

H5 페이지 생산에는 지속적인 유지 보수가 필요합니까? Apr 05, 2025 pm 11:27 PM

코드 취약점, 브라우저 호환성, 성능 최적화, 보안 업데이트 및 사용자 경험 개선과 같은 요소로 인해 H5 페이지를 지속적으로 유지해야합니다. 효과적인 유지 관리 방법에는 완전한 테스트 시스템 설정, 버전 제어 도구 사용, 페이지 성능을 정기적으로 모니터링하고 사용자 피드백 수집 및 유지 관리 계획을 수립하는 것이 포함됩니다.

58.com 작업 페이지에서 실시간 응용 프로그램 및 뷰어 데이터를 얻는 방법은 무엇입니까? Apr 05, 2025 am 08:06 AM

크롤링하는 동안 58.com 작업 페이지의 동적 데이터를 얻는 방법은 무엇입니까? Crawler 도구를 사용하여 58.com의 작업 페이지를 크롤링 할 때는이 문제가 발생할 수 있습니다.

사랑 코드 복사 및 붙여 넣기 복사하여 사랑 코드를 무료로 붙여 넣으십시오. Apr 04, 2025 am 06:48 AM

코드 복사 및 붙여 넣기는 불가능하지는 않지만주의해서 처리해야합니다. 코드의 환경, 라이브러리, 버전 등과 같은 종속성은 현재 프로젝트와 일치하지 않으므로 오류 또는 예측할 수없는 결과를 초래할 수 있습니다. 파일 경로, 종속 라이브러리 및 Python 버전을 포함하여 컨텍스트가 일관되게 유지하십시오. 또한 특정 라이브러리의 코드를 복사 및 붙여 넣을 때 라이브러리 및 해당 종속성을 설치해야 할 수도 있습니다. 일반적인 오류에는 경로 오류, 버전 충돌 및 일관되지 않은 코드 스타일이 포함됩니다. 성능 최적화는 코드의 원래 목적 및 제약에 따라 재 설계 또는 리팩토링되어야합니다. 복사 코드를 이해하고 디버그하고 맹목적으로 복사하여 붙여 넣지 않는 것이 중요합니다.

See all articles