链表

链表

视频

链表

链表的实现

数据区+链接区

链接区,下一个节点的位置

单链表操作

is_empty() 链表是否为空
length() 链表长度
travel() 遍历整个链表
add(item) 链表头部添加元素
append(item) 链表尾部添加元素
insert(pos,item) 指定位置添加元素
search(item)     查找节点是否存在

单链表结点

python交换两个变量

a = 10  //产生一个变量 a 把 10放在里面
b = 20
a,b = b,a

地址指向

指向的地址。

a = 10  
// a 代表的是内存,它内存中保存的是一个地址,地址指向什么,a的变量就是谁的

PYthon变量的本质

python基础(5):深入理解 python 中的赋值、引用、拷贝、作用域

结点串到链表上。

两个类,链表类和结点类。

这两个类之间的关系。

为空

def is_empty(self):
        #链表是否为空,self对象属性
        return self._head == None #返回和None的值,相等就为空,true

长度

链表中存在多少个结点。

current 指针,当前的位置。

def length(self):
        #链表长度
        # cur 游标,用来移动遍历节点
        cur = self._head  #指向起始节点
        # count 记录数量
        count = 0 
        while cur != None:     #判断最后的位置 cur.next == None
            count += 1 
            cur = cur.next
        return count 

遍历

def travel(self): 
        #遍历整个链表
        cur = self._head
        while cur != None:
            print cur.elem
            cur = cur.next

头部添加结点

一开始

def add(self, item):

    # 链表头部添加元素 头插法
    # 插入的新节点的next 指向 _head 指向的 next,然后 head 指向插入的新节点
    # 考虑空链表
    node = Node(item)     #初始化一个节点
    node.next = self._head
    self._head = node

指定位置添加

def insert(self,pos,item):

    #指定位置添加元素
    # pos 参数 from 0 insert(2,400) node(400)
    # pre ,指定位置的前一个元素
    if pos < 0:
        # 设置为头插法
        self.add(item)
    elif pos > self.length()-1:
        #设置尾部添加
        self.append(item)
    else:

        pre = self._head  # 指向的结点,赋予 pre
        count = 0
        while count < (pos-1):
            count = count + 1
            pre = pre.next
        #循环退出后,pre 指向 pos -1
        node = Node(item)
        node.next = pre.next
        pre.next = node

测试

 ll.append(1)
print ll.is_empty()
print ll.length()
ll.append(2)
ll.add(8)
ll.append(3)
ll.append(4)
# 8 1 2 3 4
ll.insert(-1,9)
ll.travel()
ll.insert(3,10)
ll.travel()
ll.insert(14, 12)
ll.travel()

结果

True
0
False
1
9 8 1 2 3 4 
9 8 1 10 2 3 4 
9 8 1 10 2 3 4 12 

查找

一个游标从头结点开始,进行比对。

def search(self,item):
    # 查找节点是否存在
    cur = self._head
    while cur != None:
        if cur.elem == item:
            return True
        else:
            cur = cur.next
    return False

代码

# -*- coding:utf-8 -*-
__author__ = '504'
__date__ = '2018/4/24 14:36'

class Node(object):
    # 结点类
    def __init__(self, elem):
        # 构造函数初始化 item
        self.elem = elem  # 结点一个属性,保存数据
        self.next = None  # 结点位置初始为空,链接域为空

class SingleLinkList(object):
    # 链表
    def __init__(self,node=None):  # 构造函数
        self._head = node  # 私有属性,初始化

    def is_empty(self):
        # 链表是否为空,self对象属性
        return self._head == None  #返回和None的值,相等就为空,true

    def length(self):  # 链表长度

        # cur 游标,用来移动遍历节点
        cur = self._head
        # 指向头节点
        # count 记录数量
        count = 0
        while cur != None:  # 判断最后的位置 cur.next == None
            count += 1
            cur = cur.next
        return count

    def travel(self):

        # 遍历整个链表
        cur = self._head
        while cur != None:
            print cur.elem,
            cur = cur.next
        print ""

    def add(self, item):

        # 链表头部添加元素 头插法
        # 插入的新节点的next 指向 _head 指向的 next,然后 head 指向插入的新节点
        # 考虑空链表
        node = Node(item)     #初始化一个节点
        node.next = self._head
        self._head = node



    def append(self, item):
        # 链表尾部添加元素,尾插法


        node = Node(item)
        if self.is_empty():
            self._head = node
        else:
            cur = self._head  # None
            while cur.next != None:
                cur = cur.next
            cur.next = node

    def insert(self,pos,item):

        #指定位置添加元素
        # pos 参数 from 0 insert(2,400) node(400)
        # pre ,指定位置的前一个元素
        if pos < 0:
            # 设置为头插法
            self.add(item)
        elif pos > self.length()-1:
            #设置尾部添加
            self.append(item)
        else:

            pre = self._head  # 指向的结点,赋予 pre
            count = 0
            while count < (pos-1):
                count = count + 1
                pre = pre.next
            #循环退出后,pre 指向 pos -1
            node = Node(item)
            node.next = pre.next
            pre.next = node



    def remove(self, item):
        # 删除节点
        # pre.next = cur.next
        cur = self._head
        pre = None
        while cur != None:
            if cur.elem == item:
                #删除结点
                #先判断此结点是否是头结点
                if cur == self._head:
                    self._head = cur.next

                else:
                    pre.next = cur.next
                break  # 删除后退出循环
            else:
                pre = cur
                cur = cur.next


    def search(self,item):
        # 查找节点是否存在
        cur = self._head
        while cur != None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False


if __name__ == "__main__":
    ll = SingleLinkList()  # 构造对象
    print ll.is_empty()
    print ll.length()

    ll.append(1)
    print ll.is_empty()
    print ll.length()
    ll.append(2)
    ll.add(8)
    ll.append(3)
    ll.append(4)
    # 8 1 2 3 4
    ll.insert(-1,9)
    ll.travel()
    ll.insert(3,10)
    ll.travel()
    ll.insert(14, 12)
    ll.travel()
    ll.remove(12)
    ll.travel()

结果

True
0
False
1
9 8 1 2 3 4 
9 8 1 10 2 3 4 
9 8 1 10 2 3 4 12 
9 8 1 10 2 3 4 

Process finished with exit code 0

实现无序列表:链表

Implementing an Unordered List: Linked Lists

一些项被随机的放置,如果在每一项中保持一些明确的信息,即下一项的位置。每个项的相对位置可以通过简单地从一个项到下一个项的链接来表示。

指定链表中的第一个位置,一旦知道第一项在哪里,第一项可以告诉我们第二项是什么。外部引用通常被称为链表的头,最后一项需要知道没有下一项。

Node 类

链表实现的基本构造是节点。每个节点对象必须保存两个信息,节点必须包含列表项本身,将这个称为节点的数据字段。每个节点必须保存对下一个节点的引用。

要构造一个节点,需要提供该节点的初始数据值。

#!/usr/bin/python
# -*- coding:utf-8 -*-

class Node:
    def __init__(self,initdata):
        self.data = initdata      #初始化
        self.next = None    # None 在 Node类和链表本身发挥重要作用,引用None代表没有下一个节点

    def getData(self):
        return self.data  #获取该位置值

    def getNext(self):
        return self.next

    def setData(self,newdata):
        self.data = newdata

    def setNext(self,newnext):
        self.next = newnext


class UnorderedList:
    def __init__(self):
        self.head = None



temp = Node(93)
print temp.getData()      

赋值语句将产生一个包含值93的节点对象。

会用下图表示一个节点对象。Node类还包括访问、修改数据和访问下一个引用的常用方法。

Unordered List 类

无序列表将从一个节点构建,每个节点通过显示引用链接到下一个节点。

文章

Python实现数据结构中的单链表,循环单链表,双链表

python数据结构-链表

python数据结构之链表(一)

链表