Java code: data structures, algorithms, and OOP.
Charles Reid a4539ac214 adding images for linked list explanations 2 years ago
..
img adding images for linked list explanations 2 years ago
CLinkedList.java add rotate to linked list test. 2 years ago
DLinkedList.java reorganizing doubly-linked list class DLinkedList and expanding tests. 2 years ago
IntList.java Clearing up the print method of the generic and non-generic linked lists. 2 years ago
Makefile Update makefile to make timing test 2 years ago
README.md adding wisdom learned from linked list scaling. 2 years ago
SimpleIntList.java moving linked list materials to new directory. 2 years ago
TLinkedList.java update rotate mehtod 2 years ago
Tim.java bringing Tim into the 21st century. 2 years ago
Timing.java add reverse, rotate, and tests for both. 2 years ago
output.txt updating output.txt for linked lists. 2 years ago

README.md

Lists

Abstract List Type

The list abstract data type (ADT) implements the following methods:

  • size
  • isEmpty
  • first
  • last
  • addFirst
  • addLast
  • removeFirst

Other convenience methods:

  • remove
  • removeFirst
  • removeLast
  • removeElement

Mistakes Learnings Tricks

Use the Integer class when processing integers!

When you have a String and you want an integer:

  • Integer.parse(“525”)

When you have an integer and you want a String:

  • Integer.toString(str)

In general, you can also use the String class to turn the object into a String:

  • String.valueOf(o)

Linked List specific details:

  • Need to handle cases where you are adding to an empty list, or removing last item from list
  • Especially when using tail pointer, be aware of what it is pointing to and when it needs to be updated.

Linked list methods should automatically become a list of bookkeeping things to do.

  • Add method: consider adding to an empty list, non-empty list
  • Add at index i:
    • What are all possible cases?
    • i is too big, i is too small
    • the list is empty
    • i is a special case
    • how can we fold any of these cases into other cases (list empty -> i too small)

Size of linked list:;

  • Number of bytes:
  • Size estimation:
    • 1000-integer linked list should theoretically use up:
    • 1000 nodes x ( 4 bytes per integer + 8 bytes per ref + 16 bytes object overhead )
    • 28,0000 bytes ~ 28 kB
    • What’s the power of 2 that would correspond to that?
    • 1000 integers ~ 1024 integers ~ 2^10 integers
    • Round it up to 8 bytes per integer, 8 bytes per ref, 16 bytes per object overhead)
    • 2^5 = 32 bytes per integer
    • 32 x 8 = 2^5 * 2^3 = 2^8 = 256 bits = 256 zeroes and ones
    • 10 GB / 10 kB/obj = 10x10^6 / 10 = 10^6

Exceptions:

class Empty extends Exception{};

Circular linked list:

  • Take care with the details of pointers.

Doubly linked list:

  • It makes algorithms easier, but

Nice link explaining sizes of Strings in memory:

sizeof(string) =
8 + // object header used by the VM
8 + // 64-bit reference to char array (value)
8 + string.length() * 2 + // character array itself (object header + 16-bit chars)
4 + // offset integer
4 + // count integer
4 + // cached hash code

Timing:

  • Don’t do logarithmic size………
  • Need to fix that actually.
  • Cover a single order of magnitude, then maybe try for two.