linked list implementation in python

gistfile1.py

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

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

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.

tnx

txs

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

Thanks bro :D

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.

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

Thanks!

node.next.prev = node

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

Thanks useful gist!

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

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;

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

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

https://github.com/janoop/pyLinkList

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

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