鏈表

 '# -*- coding: utf-8 -*-'

class Lnode(object):
    # data:節(jié)點保存的數(shù)據(jù)
    # next:相當(dāng)于next指針俺叭,指向下一個節(jié)點
    def __init__(self, data, pnext=None):
        self.data = data
        self.next = pnext

    def __repr__(self):
        # 用來定義node的字符輸出
        return str(self.data)


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

    # 在鏈表頭部添加節(jié)點
    def prepend(self, value):
        if self.head is None:
            self.head = Lnode(value, None)
        else:
            newhead = Lnode(value, None)
            newhead.next = self.head
            self.head = newhead
            self.length += 1

    # 在鏈表尾部添加節(jié)點
    def append(self, value):
        if self.head is None:
            self.head = Lnode(value, None)
        else:
            cursor = self.head
            while cursor.next is not None:
                cursor = cursor.next
            cursor.next = Lnode(value, None)
            self.length += 1

    # 在鏈表的指定位置插入節(jié)點
    def insert(self, index, value):
        if self.head is None and index != 1:
            return
        if index <= 0 or index > self.getlength():
            return
        elif index == 1:
            self.prepend(value)
        elif index == self.getlength():
            self.append(value)
        else:
            cursor = self.head
            node = Lnode(value, None)
            for i in range(1, index - 1):
                cursor = cursor.next
            node.next = cursor.next
            cursor.next = node

    # 刪除指定位置的節(jié)點
    def delnode(self, index):
        if self.head is None:
            return
        if index <= 0 or index > self.getlength():
            return
        elif index == 1:
            self.head = self.head.next
            self.length -= 1
        elif index == self.getlength():
            cursor = self.head
            for i in range(1, self.getlength() - 1):
                cursor = cursor.next
            cursor.next = None
            self.length -= 1
        else:
            cursor = self.head
            for i in range(1, index - 1):
                cursor = cursor.next
            t = cursor.next
            cursor.next = t.next
            self.length -= 1

    # 刪除值為value的鏈表節(jié)點元素
    def delvalue(self, value):
        if self.head is None:
            return
        elif self.head.data == value:
            self.head = self.head.next
            self.length -= 1
        else:
            pre = self.head
            cursor = pre.next
            while cursor is not None:
                if cursor.data == value:
                    pre.next = cursor.next
                    cursor = cursor.next
                    self.length -= 1
                else:
                    pre = cursor
                    cursor = cursor.next

    # 按序號查找節(jié)點值
    def getindex(self, index):
        if self.head is None:
            return
        elif index <= 0 or index > self.getlength():
            return
        elif index == 1:
            return self.head.data
        else:
            cursor = self.head
            for i in range(1, index):
                cursor = cursor.next
            return cursor.data
        # else:
        #     counter = 1
        #     cursor = self.head
        #     while cursor is not None:
        #         if index == counter:
        #             return cursor.data
        #         else:
        #             counter += 1
        #             cursor = cursor.next

    # 求鏈表的長度
    def getlength(self):
        if self.head is None:
            return 0
        else:
            count = 1
            cursor = self.head
            while cursor.next is not None:
                count += 1
                cursor = cursor.next
        return count

    # 單鏈表逆序
    def diverse(self):
        if self.head is None:
            return
        elif self.head.next is None:
            return self.head
        else:
            pre = None
            cursor = self.head
            while cursor is not None:
                ne = cursor.next
                cursor.next = pre
                pre = cursor
                cursor = ne
            self.head = pre

    # 刪除鏈表中重復(fù)元素
    def delrepret(self):
        if self.head is None:
            return
        if self.head.next is None:
            return self.head
        else:
            data = self.head.data
            # print(data)
            count = 1
            dic = {data: 1}
            pre = self.head
            cursor = pre.next
            while cursor is not None:
                print(cursor.data)
                if dic.get(cursor.data) is None:
                    dic[cursor.data] = dic.setdefault(cursor.data, 1)
                    pre = cursor
                    cursor = cursor.next
                    print(dic)
                else:
                    pre.next = cursor.next
                    cursor = cursor.next
                    self.length -= 1

    # 判斷鏈表是否為空
    def isempty(self):
        if self.head is None or self.getlength() == 0:
            return True
        else:
            return False

    # 刪除列表
    def dellist(self):
        if self.head is None or self.getlength() == 0:
            return
        else:
            cursor = self.head
            while cursor is not None:
                cursor.data = None
                cursor = cursor.next
            self.head = None

    # 打印鏈表元素
    def print(self):
        if self.head is None:
            return
        else:
            cursor = self.head
            while cursor is not None:
                print(cursor.data, end=' ')
                cursor = cursor.next
            print()


if __name__ == "__main__":

    linklist = Linklist()
    print(linklist.isempty())
    for i in range(1, 5):
        linklist.append(i)
    linklist.prepend(1)
    linklist.print()
    print("按序號查找")
    print(linklist.getindex(4))
    print("&&&&&&&&&&&&&&&&")
    linklist.insert(3, 5)
    linklist.print()
    linklist.insert(1, 1)
    linklist.print()
    linklist.insert(2, 2)
    print(linklist.isempty())
    linklist.print()
    print("刪除重復(fù)元素")
    linklist.delrepret()
    print("輸出刪除元素后的鏈表")
    linklist.print()
    # linklist.diverse()
    # linklist.print()
    linklist.delnode(5)
    # linklist.delvalue(5)
    # print("&&&&&&&&&&&&")
    # linklist.print()
    # print("**********")
    # linklist.dellist()
    # print("@@@@@@@@@@@@")
    # length = linklist.getlength()
    # print(length)
    linklist.print()
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市娘香,隨后出現(xiàn)的幾起案子根时,更是在濱河造成了極大的恐慌镜豹,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,946評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異纯赎,居然都是意外死亡,警方通過查閱死者的電腦和手機南蹂,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,336評論 3 399
  • 文/潘曉璐 我一進(jìn)店門犬金,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人六剥,你說我怎么就攤上這事晚顷。” “怎么了疗疟?”我有些...
    開封第一講書人閱讀 169,716評論 0 364
  • 文/不壞的土叔 我叫張陵该默,是天一觀的道長。 經(jīng)常有香客問我策彤,道長栓袖,這世上最難降的妖魔是什么顿膨? 我笑而不...
    開封第一講書人閱讀 60,222評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮叽赊,結(jié)果婚禮上恋沃,老公的妹妹穿的比我還像新娘。我一直安慰自己必指,他們只是感情好囊咏,可當(dāng)我...
    茶點故事閱讀 69,223評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著塔橡,像睡著了一般梅割。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上葛家,一...
    開封第一講書人閱讀 52,807評論 1 314
  • 那天户辞,我揣著相機與錄音,去河邊找鬼癞谒。 笑死底燎,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的弹砚。 我是一名探鬼主播双仍,決...
    沈念sama閱讀 41,235評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼桌吃!你這毒婦竟也來了朱沃?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,189評論 0 277
  • 序言:老撾萬榮一對情侶失蹤茅诱,失蹤者是張志新(化名)和其女友劉穎逗物,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體瑟俭,經(jīng)...
    沈念sama閱讀 46,712評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡翎卓,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,775評論 3 343
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了尔当。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片莲祸。...
    茶點故事閱讀 40,926評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖椭迎,靈堂內(nèi)的尸體忽然破棺而出锐帜,到底是詐尸還是另有隱情,我是刑警寧澤畜号,帶...
    沈念sama閱讀 36,580評論 5 351
  • 正文 年R本政府宣布缴阎,位于F島的核電站,受9級特大地震影響简软,放射性物質(zhì)發(fā)生泄漏蛮拔。R本人自食惡果不足惜述暂,卻給世界環(huán)境...
    茶點故事閱讀 42,259評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望建炫。 院中可真熱鬧畦韭,春花似錦、人聲如沸肛跌。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,750評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽衍慎。三九已至转唉,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間稳捆,已是汗流浹背赠法。 一陣腳步聲響...
    開封第一講書人閱讀 33,867評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留乔夯,地道東北人砖织。 一個月前我還...
    沈念sama閱讀 49,368評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像驯嘱,于是被迫代替她去往敵國和親镶苞。 傳聞我的和親對象是個殘疾皇子喳坠,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,930評論 2 361

推薦閱讀更多精彩內(nèi)容