Databases
StackOverflow2013
Postsdbo
POLinked List Concatenation
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POLinked List Concatenation
    primarykey
    data
    text
    <p>Working on creating linked lists for an assignment and one requirement is a method named <em>concat</em> which takes a list parameter and appends it to the end of the current list. It's not necessary for this method to use recursion, but our programs are supposed to use recursion heavily. I'm just wondering if it's even possible to come up with a recursive algorithm for this. Our list classes only have a head node, nothing else, and they're not doubly linked.</p> <p>My current attempt can only append the first value recursively. I know what it's doing wrong, but I can't come up with a solution. The first method is what's actually called on a list with a list being passed in to "concatenate". I then attempt to find the tail of the list and pass these in to the recursive method. This "wrapper" method is a mandatory requirement for our recursive methods. Here's my attempt, but it's obviously failing since I'm having trouble advancing the node reference "pt" to the next node in the list once all of the calls pop off the stack and then re-entering recursive calls to <em>concat</em>. If this <strong>is</strong> possible with recursion, can you please give me an idea of how to advance this value down the first list and re-enter the recursive calls or maybe just a better general approach towards this problem? Thanks for your time.</p> <pre><code>public void concat(MyString list1) { CharacterNode tail = null, pt = list1.head; // Find the tail of the list if (pt == null) { } else if (pt.getNext() == null) { tail = pt; } else { while (pt.getNext() != null) { pt = pt.getNext(); } tail = pt; } list1.head = concat(list1.head, tail, list1.head); } private static CharacterNode concat(CharacterNode lhead, CharacterNode tail, CharacterNode pt) { // Pass in smaller list every time // Head traverses down list till the end // Add new node with (pt's letter, null link) if (lhead == null) { // If head is null, we need to add the node lhead = new CharacterNode(pt.getCharacter(),null); } else if (tail.getNext() == lhead) { // If the head is past tail, stop } else { // Call concat on a smaller list lhead.setNext(concat(lhead.getNext(),tail,pt)); } return lhead; } </code></pre> <p>Here's CharacterNode:</p> <pre><code>class CharacterNode { private char letter; private CharacterNode next; public CharacterNode(char ch, CharacterNode link) { letter = ch; next = link; } public void setCharacter(char ch) { this.letter = ch; } public char getCharacter() { return letter; } public void setNext(CharacterNode next) { this.next = next; } public CharacterNode getNext() { return next; } } </code></pre> <p>MyString:</p> <pre><code>class MyString { // member variable pointing to the head of the linked list private CharacterNode head; // default constructor public MyString() { } // copy constructor public MyString(MyString l) { } // constructor from a String public MyString(String s) { } // for output purposes -- override Object version // no spaces between the characters, no line feeds/returns public String toString() { } // create a new node and add it to the head of the list public void addHead(char ch) { } // create a new node and add it to the tail of the list -- "wrapper" public void addTail(char ch) { } // Recursive method for addTail private static CharacterNode addTail(CharacterNode L, char letter) { } // modify the list so it is reversed public void reverse() { } // remove all occurrences of the character from the list -- "wrapper" public void removeChar(char ch) { } // Recursive removeChar method private static CharacterNode removeChar(CharacterNode n, char letter) { } // "wrapper" for recursive length() public int length() { } // Returns the length of the linked list private static int length(CharacterNode L) { } // concatenate a copy of list1 to the end of the list public void concat(MyString list1) { } // recursive method for concat private static CharacterNode concat(CharacterNode lhead, CharacterNode tail, CharacterNode pt) { } } </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USstevenelberger
    1. USstevenelberger
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POLinked List Concatenation
      1. This table or related slice is empty.
      1. VTUpMod
    1. COWe can't answer this unless we see the definition of MyString and CharacterNode.
      singulars
      1. POLinked List Concatenation
      1. USIngo
    2. COAs a side note since recursion is a key concept for your program (and you ask if using recursion is possible for your situation), anything you can do iteratively (with loops), you can also do recursively, and vice versa.
      singulars
      1. POLinked List Concatenation
      1. USajp15243
    3. CO@Ingo added both of them for you!
      singulars
      1. POLinked List Concatenation
      1. USstevenelberger
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload