Thông tin

Tác giả Aubry François
Hạn chót Không có hạn chót
Giới hạn nộp bài Không có giới hạn

Đăng nhập

Data Structures - Linked list

Linked lists are great data structures if you want to be able to perform the following operations efficiently:

1. Add an element to the start or end of the list Time complexity: \(O(1)\).

2. Remove the first or the last element of the list Time complexity: \(O(1)\).

3. Get the first and last elements on the list Time complexity: \(O(1)\).

4. Get the number of elements stored in the list Time complexity: \(O(1)\).

5. Iterate over all elements in the list. Time complexity: \(O(n)\) where \(n\) is the number of elements on the list.

All these operations can be perfomed optimal time. This means that operations 1., 2., 3., 4. are perfomed in constant time and operation 5. is performed in linear time. Note that operation 5. could not be faster since we cannot get away without inspecting each element in order to iterate over all elements.

Download the following program and execute it on this input

This program simply reads lines until an end of file is reached. When reading files from the standard input you can signal the end of file by clicking ctrl + d on Linux or OS X. On Windows use ctrl + z.

After reading the input, the program will perform the following steps:

  1. Print the number of lines
  2. Print all the lines
  3. Print the first and last lines
  4. Remove the first and last lines
  5. Print the first and last lines

Thus, you should get the following output:

4
line1
line2
line3
line4
first: line1
last: line4
new first: line2
new last: line3

The LinkedList class offers others methods. But we strongly recommend that you stick to these ones and you usually want to use such a linked list only when the above operations are the set of operations that you want to perform on your data. More other kinds of operations there are probably other data structures that are more suited.


NEVER USE LINKED LISTS IF YOU WANT TO ACCESS YOUR ELEMENTS BY INDEX OR VALUE

A common example that we often see students do, is to call the method public E get(int index). This method will return the element at position index in the list. So, for instance, after reading 4 lines, you can get each of those lines by calling list.get(0), list.get(1), list.get(2) and list.get(3). This is a very bad idea since in constrast with, for instance, an array, this funtion does not run in constant time. Instead it runs in linear time \(O(n)\) where \(n\) is the number of elements in the list.

The same is true for accessing elements by value int indexOf(Object o) or checking whether the list contains a given element with boolean contains(Object o). Never use these methods unless efficieny is not a concern for the problem your are solving (which is rarely the case...)

Note: It is possible to actually implement some of these methods efficiently using position aware linked lists but this is not really useful as we will see other simples data structures for achieving this.


In the next task, we will teach you how to implement linked lists because we believe that it is educational to do so and is a good skill to have when trying to develop more complex data structures.

However, unless the problem really requires you to be able to access the internal structure of the linked list, in a contest situation you should use the implementation provided by the language that you are using. This will save a good amount of time and help you avoid bugs in you implementation.

We thus recommender that you linked lists when the operations required on your data are the ones mentioned above. In Java that roughly corresponds to limiting yourself to using the following methods:

  1. addFirst(E e), addLast(E e)
  2. removeFirst(), removeLast()
  3. getFirst(), getLast()
  4. toString(), size()
  5. Iterating ovar all elements with for(E e : myList) { ... } where E is the type of the elements on the list.

Broken editor

You are typing some text on a broken text editor. Usually, when you type a character, that character is appended to the end of the current text that you typed so far. So that, for instance, after typing abc when you type d you will get abcd.

However, something is wrong with your text editor and sometimes your it starts writting the characters at the beginning of the text instead. And then, sometimes if goes back to normal.

You will be given a list of events comprising three types of events:

  1. key presses
  2. the computer changes to writting at the beginning
  3. the computer back normal, writting at the end

The events are represented by a string. The key presses are represented by the character from a to z that was pressed, the bug that makes you start writting at the beginning is represented by the character < and when the computer goes back to normal it is represented by >.

Example

The event string ab<cd>e represents that the characters a and b were typed normally giving ab, then the bug occured and c and d were writted at the start yielding dcab and finally things got back to normal and character e was written at the end. The final result was dcabe.

Input

  • One line with a string \(x\) representing the events.

Output

  • One line with a string \(y\) representing the string that was written.

Constraints

  • \(1 \leq |x|, |y| \leq 50000\), where \(|s|\) represents the length of string \(s\)
  • each character of \(x\) is either a lower case letter, < or > indicating the events described above.

Sample Test Cases

Sample input 1

Sample output 1

Sample input 2

Sample output 2


Max file size: 1.0 MiB
Allowed extensions: .java, .cpp, .py