Skip to content

Instantly share code, notes, and snippets.

@ptigas
Created May 28, 2012 17:21
Show Gist options
  • Save ptigas/2820165 to your computer and use it in GitHub Desktop.
Save ptigas/2820165 to your computer and use it in GitHub Desktop.
linked list implementation in python
class Node :
def __init__( self, data ) :
self.data = data
self.next = None
self.prev = None
class LinkedList :
def __init__( self ) :
self.head = None
def add( self, data ) :
node = Node( data )
if self.head == None :
self.head = node
else :
node.next = self.head
node.next.prev = node
self.head = node
def search( self, k ) :
p = self.head
if p != None :
while p.next != None :
if ( p.data == k ) :
return p
p = p.next
if ( p.data == k ) :
return p
return None
def remove( self, p ) :
tmp = p.prev
p.prev.next = p.next
p.prev = tmp
def __str__( self ) :
s = ""
p = self.head
if p != None :
while p.next != None :
s += p.data
p = p.next
s += p.data
return s
# example code
l = LinkedList()
l.add( 'a' )
l.add( 'b' )
l.add( 'c' )
print l
l.remove( l.search( 'b' ) )
print
print l
@udoyen
Copy link

udoyen commented Aug 22, 2016

could you do append, pop, insert and index @ptigas

Copy link

ghost commented Oct 1, 2016

Useful & Great script for implementation of linked list in Python. As I like & love Python. This is really a nice thing for me. Thanks so much for this.

@areeskandari
Copy link

tnx

@MagicEthan
Copy link

txs

@vishnu7may
Copy link

vishnu7may commented Jan 26, 2017

Hi, thanks for this great sample code.
I'm new to Python.
Just wondering if the search method can be implemented the following way with fewer lines of code and if there're any flaws with it?

def search( self, k ) :
	p = self.head
	while p != None :
		if ( p.data == k ) :
			return p				
		p = p.next
	return None

@hashimshafiq
Copy link

Thanks bro :D

@Sakib37
Copy link

Sakib37 commented Feb 18, 2017

The third line in remove( self, p ) method is not correct. It should be 'p.next.prev = tmp' instead of 'p.prev = tmp'. The current 'remove' method will break the link.

@fhefh2015
Copy link

i rewrite the search method

    def search(self, k):
        p = self.head
        if p is not None:
            if p.data == k:
                return p
            while p.next is not None:
                if p.data == k:
                    return p
                p = p.next
        return None

@dvoils
Copy link

dvoils commented Mar 10, 2017

Thanks!

@vivekiyer114
Copy link

node.next.prev = node

why the above line ?? Pls someone explain..Thank you

@vatsal-sodha
Copy link

Thanks useful gist!

@Salil999
Copy link

@vivekiyer114

node.next.prev = node
why the above line ?? Pls someone explain..Thank you

You need to set the head's previous pointer to the node that we are adding in. We set the node that we are adding in as the new head and need to update the "pointers" (references, since we're doing Python) accordingly.

@praful09534
Copy link

I think according to proper implementation of doubly liked list please find below method for remove. If code is wrong please point out what is wrong in the below code.

    def remove(self, p):
             if p==None:
                #return p;
                print ('Searched Element does not exist in the defined linked list');
                return;
             if p == self.head:
                tmp = p;
                p.next.prev = p.prev;
                self.head = p.next;
             else:
                tmp = p;
                p.prev.next = p.next;
                p.next.prev = p.prev;
             del tmp;
             return;

@SarbjitGahra
Copy link

def add( self, data ) :
node = Node( data )
if self.head == None :
self.head = node
else :
node.next = self.head
node.next.prev = node
self.head = node

#everytime we add a node, we create a temp node and give it the value self.head. so we adding from the front not the back ??

@tejas-kr
Copy link

tejas-kr commented Sep 1, 2017

hey, you should explicitly mention that it is a doubly linked list.

Copy link

ghost commented Feb 15, 2018

@skaundin
Copy link

skaundin commented Dec 4, 2018

The print call will just print an object and not the linkedlist data

@dchirag
Copy link

dchirag commented Jul 10, 2019

Line 34 is is buggy and corrupting the backward list. It should be
node.next.prev = tmp

Also, for sake of completion, you need to release the instance of the node being deleted.
So add line after line 34
del p

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment