77539

Inserting in the middle of a doubly linked list- Python

Question:

I am new to stackoverflow and the Python language and have a question. I know how to implement a singly linked list in Python but am having trouble with doubly linked list, more specifically inserting into the middle of the doubly linked list. Can anyone help me with code to do this? Thank you

Answer1:

Me also, I'm new to Python, but I hope I can help you. So if I got your question correctly, suppose you have some (classic) linked list implementation like this:

# Simple LinkedList class class LinkedList: def __init__(self, data, prev=None, next=None): self.data = data self.prev = prev self.next = next # Just a string representation def __str__(self): if self.next: return '%s %s' % (str(self.data), self.next.__str__()) else: return '%s' % str(self.data)

You can easily insert an element to middle, knowing the linked list's ends, by iterating simultaneously from the ends to middle. When the iterators intersect, you add your element:

# Insert to middle logic def insertToMiddle(data, left, right): # Iterate while True: # Test for intersection if left.next is right: node = LinkedList(data, left, right) left.next = node right.prev = node return elif left is right: node = LinkedList(data, left.prev, right.next) left.next = node right.next.prev = node return # Next iteration left = left.next right = right.prev # This doesn't actually execute for a right call if not left or not right: return

Below, you can see a linked list creation, and its representation, before and after the insertion:

# Sample list creation node1 = LinkedList(1) node2 = LinkedList(2,node1) node3 = LinkedList(3,node2) node4 = LinkedList(4,node3) node1.next = node2 node2.next = node3 node3.next = node4 # Test print node1 insertToMiddle(5, node1, node4) print node1 insertToMiddle(6, node1, node4) print node1 insertToMiddle(7, node1, node4) print node1

Output:

1 2 3 4 #initial 1 2 5 3 4 #inserted 5 1 2 5 6 3 4 #inserted 6, notice it's right to middle 1 2 5 7 6 3 4 #inserted 7

Remark: If your list has an odd number of elements (say 2 3 4), inserting to middle is somehow undefined, so the above function will add immediately to middle's right (2 3 elem 4)

Recommend

  • Django database entry created by concatenation of two fields
  • Removing Python overhead when wrapping C++ vectors
  • Django Foreign Key model cant display in view JSON
  • Same file with same name getting downloaded even when provided with different URLs
  • Java ClassNotFoundException when reading object from a stream
  • Java Neo4J out of memory
  • Restrict classes that can implement interface in Java
  • Change thread priority from lowest to highest in .net
  • Readline feature in Directory Lister class
  • Swift 1.2 assigning let after initialization
  • jQuery Custom Radio Buttons not working as radio buttons
  • Index 1 is either negative or above rows count
  • Bootstrap Carousel Next/Prev not working
  • Rails CarrierWave versions are not created for some reason
  • Visualizing a large matrix in matlab
  • Change attribute of custom directive
  • Efficient algorithm to find additions and removals from 2 collections
  • What does certain JVM do after loading ByteCode into memory?
  • Should a web service response include empty values?
  • Grails calculated field in SQL
  • How to add date and time under each post in guestbook in google app engine
  • JSON with duplicate key names losing information when parsed
  • vba code to select only visible cells in specific column except heading
  • What do the 'size' numbers mean in the windbg !heap output?
  • Warning: Can't call setState (or forceUpdate) on an unmounted component
  • Return words with double consecutive letters
  • AT Commands to Send SMS not working in Windows 8.1
  • Windows forms listbox.selecteditem displaying “System.Data.DataRowView” instead of actual value
  • InvalidAuthenticityToken between subdomains when logging in with Rails app
  • KeystoneJS: Relationships in Admin UI not updating
  • trying to dynamically update Highchart column chart but series undefined
  • embed rChart in Markdown
  • apache spark aggregate function using min value
  • Django query for large number of relationships
  • Sorting a 2D array using the second column C++
  • How to get NHibernate ISession to cache entity not retrieved by primary key
  • Why is Django giving me: 'first_name' is an invalid keyword argument for this function?
  • How can I use `wmic` in a Windows PE script?
  • Unable to use reactive element in my shiny app
  • How to push additional view controllers onto NavigationController but keep the TabBar?