Linked Lists

What Are Linked Lists

Linked lists are a data structure whereby each element of a list is stored in a structure of linked wrapper objects that simply hold a data value and point to neighbor items. The list is an object that contains only one reference to the beginning of the list. Remaining elements must be obtained from the items in the list themselves.

The linked list structure can be implemented as a singly-linked list or a doubly-linked list. A singly linked list means each list node points only to the next node (or a null pointer if the end of the list). A doubly linked list means each list node points at the prior node as well as the next node.

The purpose of using linked lists is that certain operations become much faster (for example, adding elements to the front or back of a list) when using a linked object data structure than they would be using an array-based data structure, which would need to constantly shift or resize elements.

Why Linked Lists

Linked lists are a basic data structure, and the idea is a simple one, on the surface. These are excellent for testing understanding, however, because a Linked List takes practice and experience to implement correctly. This can separate the student who says "Let me try this concept out first..." and knows how to practice, from a student who says "Yes yes, I understand, it's very easy, now on to the next topic" and has not actually sat down to implement any of the basics, let alone the more advanced stuff.

Another nice feature of LinkedLists is that they are great for simple, applied recursion problems. "Do X. Okay, now do X recursively."

The Gist of Linked Lists

Questions about Linked Lists require handling a number of different assumptions, questions, and possible interfaces. Which one you implement depends on the problem and specifications. However, "Linked List" should immediately call to mind the methods in a List ADT (abstract data type) and by extension the methods in a LinkedList ADT. (See Abstract Data Types.) Linked lists are designed according to the same basic principles, but their implementation can vary.

The basic gist is this: a simple, link-based memory structure that is dynamic in size. This organization of data makes management and allocation of new memory for new data less troublesome than automatically resizing arrays. However, it makes random access impossible, sacrificing functionality for speed.

The main purpose of using linked lists is the O(1) access to add nodes to the front or back of the list.

List 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:

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

Other convenience methods:

• add
• recursive add
• remove
• remove(i)
• removeFirst
• removeLast
• recursive remove

Node type:

• Node class should be defined INSIDE list class
• private static class Node
• Node class fields: E data, Node next
• constructor with data, constructor with data plus next
• getData
• getNext
• setNext
• equals
• toString

Iterable

Java API LinkedList

Link: https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html

Add methods:

• add(e) : add element
• add(i,e) : add index i element e
• addAll(c) : add all elements from collection c
• addFirst(e)
• addLast(e)

Utility operations:

• clear()
• clone()
• contains(o)

Iterators:

• descendingIterator()
• listiterator(i)

Find:

• indexOf(o) : returns -1 if not found

Get/Set:

• get(i)
• getFirst()
• getLast()
• element() : peek operation. "Retrieves, but does not remove, the head (first element) of this list."

Remove:

• remove() : removes head
• remove(i) : remove element at index i
• removeFirst()
• removeLast()

• remove(o) : remove obj, if present
• removeFirstOccurrence(o)
• removeLastOcurrence(o)

Notes

Skiena chapter 3 questions

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

See Linked Lists/Java/Reverse

Question 3-4) Design a dictionary structure in which search, insertion, and deletion can be handled in O(1) time.

Assume set elements are from 1..n)

(Initialization can take O(n) time.)

• Well, if this search has to take O(1) time, we need to know EXACTLY where things are, given their value.
• The problem seems to indicate either a hash table, or an off-by-one array.
• Off-by-one array: the numbers passed in from 1 to n are represented in an array of length n, with the kth number represented by the k-1th cell.
• hash table: key value is given, turns into unique integer, looked up in O(1) time

Question 3-5) Find the overhead fraction (data space/total space) for each binary tree implementation on n nodes given the following conditions:

• All nodes store data, 2 child pointers, and 1 parent pointer. Data fields are 4 bytes, pointers are 4 bytes.
• Only leaf nodes store data; internal nodes store 2 child pointers. Data field requires 4 bytes, 2 bytes per pointer.

First case:

• Binary tree with n nodes -> n-1 edges
• Child/parent ppointers means 2x edges
• 2(n-1) edges, 2(n-1) pointers
• Alternatively, here's the analysis:

n nodes x (4 bytes of data/node) = 4n bytes data

n nodes x (12 bytes of pointers/node) = 12 n bytes

Total space is 16 n bytes, so overhead fraction is 1/4, i.e., the data space to total space ratio is 1/4

Second case:

• If we have n nodes, we have ~n/2 leaves
• n nodes total x (1 leaf node / 2 nodes) ~ n/2 lleaf nodes

n/2 empty nodes x (2 pointers/1 empty node) x (2 bytes/pointer) = 2n bytes for empty nodes with pointers

n/2 data nodes x (4 bytes/1 empty node) = 2n bytes data

The overhead fraction is thus 1/2: half the bytes are for data, half the bytes are for pointers.

question 3-6) Modifying balance d search tree to have O(1) successor/predecessor methods?

See Binary Trees/O1 Successor Predecessor