Linked Lists - Revision history

Admin: Replacing charlesreid1.com:3000 with git.charlesreid1.com

2019-10-09T03:35:56Z

Replacing charlesreid1.com:3000 with git.charlesreid1.com

← Older revision		Revision as of 03:35, 9 October 2019
Line 27:		Line 27:
	===LinkedList ADT===		===LinkedList ADT===

	Link to implementation on git.charlesreid1.com: https://charlesreid1.com~~:3000~~/cs/java/src/master/lists/linked-lists		Link to implementation on git.charlesreid1.com: https://git.charlesreid1.com/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:

Admin: /* Flags */

2017-09-09T17:01:29Z

Flags

← Older revision		Revision as of 17:01, 9 September 2017
Line 119:		Line 119:
	[[Category:Linked Lists]]		[[Category:Linked Lists]]

	{{~~DataStructuresFlag~~}}		{{LinkedListFlag}}

Admin: /* Implementation */

2017-09-09T17:00:54Z

Implementation

← Older revision		Revision as of 17:00, 9 September 2017
Line 101:		Line 101:


	=~~Implementation~~=		=Implementations=

	See [[Linked Lists/Java]] and [[Linked Lists/Python]]		See [[Linked Lists/Java]] and [[Linked Lists/Python]]

Admin: /* Questions */

2017-09-09T16:57:59Z

Questions

← Older revision		Revision as of 16:57, 9 September 2017
Line 100:		Line 100:
	* removeLastOcurrence(o)		* removeLastOcurrence(o)


			=Implementation=

			See [[Linked Lists/Java]] and [[Linked Lists/Python]]

	=Questions=		=Questions=

Admin: /* Questions */

2017-06-06T05:12:19Z

Questions

← Older revision		Revision as of 05:12, 6 June 2017
Line 103:		Line 103:
	=Questions=		=Questions=

	See questions from Goodrich et al Data Structures in Java book at [[Linked Lists/Java]]		See questions from Goodrich et al Data Structures in Java book at [[Linked Lists/Java#Questions]]

	==Skiena Algorithm Handbook Chapter 3 questions==		==Skiena Algorithm Handbook Chapter 3 questions==

Admin: /* Questions */

2017-06-06T05:12:00Z

Questions

← Older revision		Revision as of 05:12, 6 June 2017
Line 102:		Line 102:

	=Questions=		=Questions=

			See questions from Goodrich et al Data Structures in Java book at [[Linked Lists/Java]]

	==Skiena Algorithm Handbook Chapter 3 questions==		==Skiena Algorithm Handbook Chapter 3 questions==

Admin: /* Questions */

2017-06-06T05:11:16Z

Questions

← Older revision		Revision as of 05:11, 6 June 2017
Line 102:		Line 102:

	=Questions=		=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.)




	~~Question R-3.6) Give algorithm for finding second to last node in singly linked list in which last node indicated by null reference.~~

	Question R-3.8) Describe a method for finding the middle node of a doubly linked list with header and trailer sentinels by "link hopping," and without relying on explicit knowledge of the size of the list. In the case of an even numer ofnodes, report hte node slightly left of center as middle. WHat is the runtime of this 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.~~

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

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

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



	==Skiena Algorithm Handbook Chapter 3 questions==		==Skiena Algorithm Handbook Chapter 3 questions==

Admin: /* Skiena Algorithm Handbook Chapter 3 questions */

2017-06-05T23:23:33Z

Skiena Algorithm Handbook Chapter 3 questions

← Older revision		Revision as of 23:23, 5 June 2017
Line 132:		Line 132:


	===Skiena Algorithm Handbook Chapter 3 questions===		==Skiena Algorithm Handbook Chapter 3 questions==

	'''Question 3-2) Write a program to reverse the direction of a singly linked list in O(n) time.'''		'''Question 3-2) Write a program to reverse the direction of a singly linked list in O(n) time.'''

Admin at 23:23, 5 June 2017

2017-06-05T23:23:13Z

← Older revision		Revision as of 23:23, 5 June 2017
Line 1:		Line 1:
			=Notes=

	==What Are Linked Lists==		==What Are Linked Lists==

Line 99:		Line 101:


	=~~=Notes=~~=		=Questions=

	===Goodrich ~~chapter~~ 3===		==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.		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.
Line 107:		Line 109:
	Questions about Java arrays and lists:		Questions about Java arrays and lists:

	Question R-3.2) ~~Write Java method~~ that ~~repeatedly selects and removes~~ a ~~random entry from an array~~ until the ~~array holds no more entries~~.		===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.)

	~~See [[Arrays/Java/Repeatedly Remove]] for an algorithm to repeatedly select and remove entries from an array.~~

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

	~~[[Linked List/Java/Tail Pointer]]~~

	Question R-3.6) Give algorithm for finding second to last node in singly linked list in which last node indicated by null reference.		Question R-3.6) Give algorithm for finding second to last node in singly linked list in which last node indicated by null reference.
Line 129:		Line 132:


	===Skiena ~~chapter~~ 3 questions===		===Skiena Algorithm Handbook Chapter 3 questions===

	'''Question 3-2) Write a program to reverse the direction of a singly linked list in O(n) time.'''		'''Question 3-2) Write a program to reverse the direction of a singly linked list in O(n) time.'''

Admin: /* Skiena chapter 3 questions */

2017-06-05T21:45:26Z

Skiena chapter 3 questions

@@ Line 100: / Line 100: @@
 ==Notes==
 ===Skiena chapter 3 questions===
 '''Question 3-2) Write a program to reverse the direction of a singly linked list in O(n) time.'''