Linked List

View as PDF

Submit solution

All submissions

Best submissions

Points: 20 (partial)

Time limit: 2.5s

Java 8 4.5s

Memory limit: 10M

Java 8 12M

Author:

quantum

Problem types

1992 is a different time. It's before the time that the entire Windows division at Microsoft could only afford to get one computer with a staggering 96 MB of RAM to test Windows 95 on. The average computer back then had less than 4 MB of RAM. It's less than what modern Java requires to start up!

To secure your release back to the modern age, you came across me. I would gladly let you back to the future if only you do me one little favour. I need to implement a linked list that can store $N$ ~N~ elements, up to $1\,000\,000$ ~1\,000\,000~, each storing integers ranging from $-8 \times 10^{12}$ ~-8 \times 10^{12}~ to $8 \times 10^{12}$ ~8 \times 10^{12}~. But wait, I am not very rich! I can only afford 10 MB of RAM (remember it's 1992) to run the program.

Your linked list must support these operations:

< select the previous element (rewinding).
> select the next element (advancing).
= changes the current element to a value (updating).
+ creates a new element with a value, shifting the current element back (inserting). The pointer will point at the inserted element.
- removes the current element, shifts pointer to the next element (deleting).
! prints the value of the current element (printing).

Note that your linked list starts empty, and it is possible to delete the last element in the list. In both cases, the pointer goes beyond the end of the list. In no case will the past-the-end "element" be updated, deleted, or queried, nor will there be attempts to advance past the past-the-end "element", or rewind past the first element.

Input Specification

The first line will contain the integer $M$ ~M~, the number of operations to perform, up to $10\,000\,000$ ~10\,000\,000~.

The next $M$ ~M~ lines will contain one of the operation labels, <, >, =, +, -, or !. If the operation takes a value, in case of = or +, then the label is followed by a space followed by an integer.

Output Specification

For every ! operation, print the value at the linked list pointer.

Subtasks

There are four subtasks:

$N \le 1\,000$ ~N \le 1\,000~, $M \le 10\,000$ ~M \le 10\,000~, $10\%$ ~10\%~ of points
$N \le 10\,000$ ~N \le 10\,000~, $M \le 100\,000$ ~M \le 100\,000~, $20\%$ ~20\%~ of points
$N \le 100\,000$ ~N \le 100\,000~, $M \le 1\,000\,000$ ~M \le 1\,000\,000~, $30\%$ ~30\%~ of points
$N \le 1\,000\,000$ ~N \le 1\,000\,000~, $M \le 10\,000\,000$ ~M \le 10\,000\,000~, $40\%$ ~40\%~ of points

Sample Input

10
+ 100
+ 200
>
!
<
!
-
!
= 300
!

Sample Output

Explanation

Insert $100$ ~100~ to list: $[100]$ ~[100]~, pointer at 0.
Insert $200$ ~200~ to list: $[200, 100]$ ~[200, 100]~, pointer at 0.
Advance pointer: pointer at 1.
Print: prints $100$ ~100~ which is at index 1 of list $[200, 100]$ ~[200, 100]~.
Rewind pointer: pointer at 0.
Print: prints $200$ ~200~ which is at index 0 of list $[200, 100]$ ~[200, 100]~.
Delete element $200$ ~200~: $[100]$ ~[100]~, pointer still at 0.
Print: prints $100$ ~100~ which is at index 0 of list $[100]$ ~[100]~.
Update to $300$ ~300~: $[300]$ ~[300]~, pointer at 0.
Print: prints $300$ ~300~ which is at index 0 of list $[300]$ ~[300]~.

Warning

It might be unwise to use languages that use a lot of memory, and even more unwise to use languages that won't start in the memory limit. Your mileage may vary. Problem is guaranteed to be solvable in any language that allows direct memory access, such as C, or C++.

Comments

-1

lolzballs commented on April 5, 2015, 2:43 p.m.

Any tips on how to reduce running time? My program uses linear search to find free blocks of memory, but it fails on the last 3 batch cases.

2

quantum commented on April 5, 2015, 5:46 p.m.

You said it, there's your problem. A linked list should not have linear time operations. Please refrain from posting too much details though, it might give away too much info.

0

lolzballs commented on April 5, 2015, 12:35 a.m. ← edited →

What happens when the final element in the list gets deleted? Does the current pointer go to the new final element or does it stay at the same location?

EDIT: It stays at the same location

3

jackyliao123 commented on March 24, 2015, 1:27 p.m.

creating a long array size of 1000000 causes MLE

2

quantum commented on March 26, 2015, 9:32 p.m.

Increased time and memory limit for Java only so it can pass.

-5

FatalEagle commented on March 24, 2015, 1:35 p.m.

The problem statement specifically stated that Java won't work.

This comment is hidden due to too much negative feedback. Show it anyway.

0

lolzballs commented on March 18, 2015, 2:43 p.m.

I'm slightly confused by "In no case will there ... be attempts to advance past the past-the-end "element", or rewind past the first element."

Does this mean that once the current pointer is at the last element, there will be no attempts to use '>'? Or does it mean that it can, but after it gets there, it won't use '>' again

0

quantum commented on March 18, 2015, 2:55 p.m.

You can advance beyond the last element, but no > will be used when it is beyond the last element. This is necessary because the linked list starts empty, and points to the pseudo-element.

0

lolzballs commented on March 24, 2015, 9:08 p.m.

Can you < past the first element?

Like if there is elements 1, 2 and the current pointer is on 1, can you < to the "element" before it and prepend something there?

1

kobortor commented on March 24, 2015, 11:52 p.m.

In no case will the past-the-end "element" be updated, deleted, or queried, nor will there be attempts to advance past the past-the-end "element", or rewind past the first element.

So no.

-2

kobortor commented on Feb. 23, 2015, 7:40 p.m. ← edited →

What is $N$ ~N~ supposed to be?

-2

quantum commented on Feb. 23, 2015, 8:30 p.m. ← edited →

$N$ ~N~ is the number of elements to store.