Linked Lists/Java - Revision history

Admin at 00:09, 17 March 2019

2019-03-17T00:09:03Z

← Older revision		Revision as of 00:09, 17 March 2019
Line 7:		Line 7:
	The full list is here: List interface class abstract methods: https://docs.oracle.com/javase/8/docs/api/java/util/List.html		The full list is here: List interface class abstract methods: https://docs.oracle.com/javase/8/docs/api/java/util/List.html

	Link to implementations of various Linked Lists on on git.charlesreid1.com: https://charlesreid1.com~~:3000~~/cs/java/src/master/lists/linked-lists		Link to implementations of various Linked Lists on on git.charlesreid1.com: https://git.charlesreid1.com/cs/java/src/master/lists/linked-lists

	===LinkedList ADT===		===LinkedList ADT===
Line 33:		Line 33:
	===Singly Linked List===		===Singly Linked List===

	A basic singly linked list that forces the data type to be an integer is defined in IntList.java: https://charlesreid1.com~~:3000~~/cs/java/src/master/lists/linked-lists/IntList.java		A basic singly linked list that forces the data type to be an integer is defined in IntList.java: https://git.charlesreid1.com/cs/java/src/master/lists/linked-lists/IntList.java

	It takes quite a bit of work to get everything functioning correctly - particularly with remove operations. None of the difficulty is in the concept. It is all in the details.		It takes quite a bit of work to get everything functioning correctly - particularly with remove operations. None of the difficulty is in the concept. It is all in the details.

	Practice, review the details, document learning process/patterns/mistakes here: https://charlesreid1.com~~:3000~~/cs/java/src/master/lists/linked-lists		Practice, review the details, document learning process/patterns/mistakes here: https://git.charlesreid1.com/cs/java/src/master/lists/linked-lists

	===Generic Type Linked List===		===Generic Type Linked List===
Line 43:		Line 43:
	The next phase of implementing a linked list is to make it type-generic, so that it can utilize the diamond notation of the Java Collections library and the type protection it requires.		The next phase of implementing a linked list is to make it type-generic, so that it can utilize the diamond notation of the Java Collections library and the type protection it requires.

	Typed linked list TLinkedList<E> class: https://charlesreid1.com~~:3000~~/cs/java/src/master/lists/linked-lists/TLinkedList.java		Typed linked list TLinkedList<E> class: https://git.charlesreid1.com/cs/java/src/master/lists/linked-lists/TLinkedList.java

	===Circular Linked List===		===Circular Linked List===
Line 49:		Line 49:
	A linked list organized in a circular fashion, that can be expanded but that is efficient in its re-use of space.		A linked list organized in a circular fashion, that can be expanded but that is efficient in its re-use of space.

	Circular linked list CLinkedList<E> class: https://charlesreid1.com~~:3000~~/cs/java/src/master/lists/linked-lists/CLinkedList.java		Circular linked list CLinkedList<E> class: https://git.charlesreid1.com/cs/java/src/master/lists/linked-lists/CLinkedList.java

	===Doubly Linked List===		===Doubly Linked List===

Admin: /* Flags */

2017-06-06T05:31:12Z

Flags

← Older revision		Revision as of 05:31, 6 June 2017
Line 54:		Line 54:

	Implementation of a linked list that stores a reference to a header and trailer node, "bumper nodes" that make the implementation of various algorithms easier.		Implementation of a linked list that stores a reference to a header and trailer node, "bumper nodes" that make the implementation of various algorithms easier.

			=Questions=


			==Goodrich et al Data Structures in Java Chapter 3 questions==

			Note that Goodrich spends the first few chapters of the Java book focusing on linked lists and link-based data structures, while in the Python book the emphasis is on array lists and array-based data structures.

			Questions about Java arrays and lists:

			===Tail Pointer===

			Question R-3.5) SinglyLinkedList sets the tail field to null when deleting last node of a list. What if those lines were removed? Would class still work, and why or why not?

			Class would no longer work properly - if tail pointer is not null, will not be able to use fact that tail pointer points at null for end of list. Tail pointer is never reset to null, so dangling node will always be a dangling node until tail is explicitly reset to something else. (Some functionality may not be affected - but it depends entirely on the order of operations.)

			===Second to last===

			'''Question R-3.6) Find second to last node in singly linked list, where last node is indicated by having a null reference.'''

			To find second to last node, you're checking two nodes ahead:

			<pre>
			if(size==0 \|\| size==1) {
			// no second to last node
			}

			Node runner = this.head;
			while(runner.getNext().getNext() != null) {
			runner = runner.getNext();
			}
			// Now runner points to the node that points to the null node
			// (i.e., runner points to the second-to-last node.)
			</pre>

			===Midpoint===

			Finding the midpoint of a singly linked list:
			* Naive solution: traverse the list once, counting along the way, then traverse the list a second time
			* But, why not count twice if we can
			* Two steps with the runner, one step with the head. etc..

			Finding the midpoint of a doubly linked list:
			* In the case of an odd number of nodes, iterating head forward and tail backward will eventually have head and tail equal - pointing to same node
			* In the case of an even number of nodes, the head and tail are passing ships in the night - so we need to check if head.next == tail

			===Implementing the Size Method===

			'''Question R-3.9) Give an implementation of the size() method for the SingularlyLinkedList class, assuming that we did not maintain size as an instance variable.'''

			<pre>
			if(isEmpty()) {
			throws new Empty();
			}
			int count = 1;
			Node runner = head;
			while(runner.getNext()!=null) {
			count++;
			runner = runner.getNext();
			}
			</pre>

			'''Question R-3.10) Give an implementation of the size() method for the DoublyLinkedList class, assuming that we did not maintain size as an instance variable.'''

			<pre>
			if(isEmpty()) {
			throws new Empty();
			}
			int count = 1;
			Node hrunner = head;
			Node trunner = tail;
			while(hrunner!=trunner && hrunner.getNext()!=trunner) {
			count++; count++;
			hrunner = hrunner.getNext();
			trunner = trunner.getNext();
			}
			if(hrunner!=trunner) {
			// the pointers don't match - even number of elements
			count--;
			}

			// This handles the empty DLL, the one-element DLL, the two-element DLL, the three-element DLL
			</pre>

			'''Question R-3.11) Give an implementation of the size() method for the CircularlyLinkedList class, assuming that we did not maintain size as an instance variable.'''



			===Rotate===

			Question R-3.12) Implement a rotate() method in the SinglyLinkedList class, which has semantics equal to addLast(removeFirst()) but which does not create any new node.




	=Flags=		=Flags=

Admin: /* Circular Linked List */

2017-06-03T07:30:54Z

Circular Linked List

← Older revision		Revision as of 07:30, 3 June 2017
Line 38:		Line 38:

	Practice, review the details, document learning process/patterns/mistakes here: https://charlesreid1.com:3000/cs/java/src/master/lists/linked-lists		Practice, review the details, document learning process/patterns/mistakes here: https://charlesreid1.com:3000/cs/java/src/master/lists/linked-lists

			===Generic Type Linked List===

			The next phase of implementing a linked list is to make it type-generic, so that it can utilize the diamond notation of the Java Collections library and the type protection it requires.

			Typed linked list TLinkedList<E> class: https://charlesreid1.com:3000/cs/java/src/master/lists/linked-lists/TLinkedList.java

	===Circular Linked List===		===Circular Linked List===

	A linked list organized in a circular fashion, that can be expanded but that is efficient in its re-use of space.		A linked list organized in a circular fashion, that can be expanded but that is efficient in its re-use of space.

			Circular linked list CLinkedList<E> class: https://charlesreid1.com:3000/cs/java/src/master/lists/linked-lists/CLinkedList.java

	===Doubly Linked List===		===Doubly Linked List===

Admin: /* Single Linked List */

2017-06-03T07:28:36Z

Single Linked List

← Older revision		Revision as of 07:28, 3 June 2017
Line 29:		Line 29:
	See Java API for LinkedList class: https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html		See Java API for LinkedList class: https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html

	==~~Single Linked List~~==		==Code Implementation==

	~~A no-nonsense type-overhead object is defined in IntList.java: https://charlesreid1.com:3000/cs/java/src/master/lists/linked-lists/IntList.java~~		===Singly Linked List===

	~~It takes quite a bit of work~~ to ~~get everything functioning correctly~~ - ~~particularly with remove operations~~.		A basic singly linked list that forces the data type to be an integer is defined in IntList.java: https://charlesreid1.com:3000/cs/java/src/master/lists/linked-lists/IntList.java

	Practice, review the details, document ~~learnings~~/patterns/mistakes here: https://charlesreid1.com:3000/cs/java/src/master/lists/linked-lists		It takes quite a bit of work to get everything functioning correctly - particularly with remove operations. None of the difficulty is in the concept. It is all in the details.

			Practice, review the details, document learning process/patterns/mistakes here: https://charlesreid1.com:3000/cs/java/src/master/lists/linked-lists

			===Circular Linked List===

			A linked list organized in a circular fashion, that can be expanded but that is efficient in its re-use of space.

			===Doubly Linked List===

			Implementation of a linked list that stores a reference to a header and trailer node, "bumper nodes" that make the implementation of various algorithms easier.

	=Flags=		=Flags=

Admin: /* List Interfaces in Java API */

2017-06-03T00:55:57Z

List Interfaces in Java API

← Older revision		Revision as of 00:55, 3 June 2017
Line 6:		Line 6:

	The full list is here: List interface class abstract methods: https://docs.oracle.com/javase/8/docs/api/java/util/List.html		The full list is here: List interface class abstract methods: https://docs.oracle.com/javase/8/docs/api/java/util/List.html



	Link to implementations of various Linked Lists on on git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/lists/linked-lists		Link to implementations of various Linked Lists on on git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/lists/linked-lists

Admin: /* Single Linked List */

2017-06-01T06:15:13Z

Single Linked List

← Older revision		Revision as of 06:15, 1 June 2017
Line 36:		Line 36:

	It takes quite a bit of work to get everything functioning correctly - particularly with remove operations.		It takes quite a bit of work to get everything functioning correctly - particularly with remove operations.

			Practice, review the details, document learnings/patterns/mistakes here: https://charlesreid1.com:3000/cs/java/src/master/lists/linked-lists

	=Flags=		=Flags=

Admin: /* LinkedList ADT */

2017-06-01T06:14:44Z

LinkedList ADT

← Older revision		Revision as of 06:14, 1 June 2017
Line 8:		Line 8:



			Link to implementations of various Linked Lists on on git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/lists/linked-lists

	===LinkedList ADT===		===LinkedList ADT===

	~~Link to implementation on git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/lists/linked-lists~~

	The linked list abstract data type provides the following methods:		The linked list abstract data type provides the following methods:
Line 30:		Line 30:

	See Java API for LinkedList class: https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html		See Java API for LinkedList class: https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html

			==Single Linked List==

			A no-nonsense type-overhead object is defined in IntList.java: https://charlesreid1.com:3000/cs/java/src/master/lists/linked-lists/IntList.java

			It takes quite a bit of work to get everything functioning correctly - particularly with remove operations.

	=Flags=		=Flags=

Admin: /* LinkedList ADT */

2017-06-01T06:12:57Z

LinkedList ADT

← Older revision		Revision as of 06:12, 1 June 2017
Line 29:		Line 29:
	* removeLast		* removeLast

	See Java API for LinkedList class: https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html		See Java API for LinkedList class: https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html

	=Flags=		=Flags=

Admin: /* List ADT */

2017-06-01T06:12:45Z

List ADT

← Older revision		Revision as of 06:12, 1 June 2017
Line 1:		Line 1:
	==List ADT==		==List Interfaces in Java API==

			===List ADT===

			The List interface - adding <code>implements List<E></code> to a class - has quite a few methods that need to be defined. This makes a data collection capable of being treated as a Collections object.

			The full list is here: List interface class abstract methods: https://docs.oracle.com/javase/8/docs/api/java/util/List.html



	===LinkedList ADT===		===LinkedList ADT===

Admin: /* LinkedList ADT */

2017-06-01T05:12:54Z

LinkedList ADT

← Older revision		Revision as of 05:12, 1 June 2017
Line 21:		Line 21:
	* removeLast		* removeLast

			See Java API for LinkedList class: https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html

	=Flags=		=Flags=