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
@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