Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Data Structure to Implement Text Editor?

Recently I was asked this question in an interview. The exact question was

What data structures will you use to implement a text editor. Size of editor can be changed and you also need to save the styling information for all the text like italic, bold etc ?

At that point of time, I tried to convince him using many different approaches like stack, Doubly Linked list and all.

From that point of time,This question is bugging me.

like image 548
Geek_To_Learn Avatar asked Aug 25 '15 18:08

Geek_To_Learn


People also ask

What data structure is used for text editor?

The gap buffer data structure is commonly used by text editors for storing the files that are currently being edited. The data structure is simply an array that stores the contents of a file plus some extra empty space. This empty space is called the gap.

Which data structure does Vim use?

For example, the original vi used an array of lines, which sort of explains some of its quirky line-oriented idioms. The BSD clone of vi, nvi, uses an entire database to represent buffers. Vim uses a fairly complex rope-like data structure with page-oriented blocks, which may be stored out-of-order in its swap file.

Do text editors use linked lists?

This program implements a text editor using Linked List and Stack data structures. Each line of text is saved into a linked list node, which consists of a data portion holding the text and a pointer to the next node of the linked list, which is the next line of the text.


2 Answers

It looks like they'd like to know if you were aware of the flyweight pattern and how to use it correctly.

A text editor is a common example while describing that pattern.

Maybe your interviewer was a lover of the GOF book. :-)

like image 133
skypjack Avatar answered Oct 22 '22 01:10

skypjack


In addition to the previous answers, I would like to add that in order to get to the data structures, you need first to know your design - otherwise the options will be too broad selected.

As example let's assume that you'll need an editing functionality. Here the State and Memento design patterns will be a good fit. Very suitable structure will be the Cord, since it's

composed of smaller strings that is used for efficiently storing and manipulating a very long string.

In our case the text editing program

may use a rope to represent the text being edited, so that operations such as insertion, deletion, and random access can be done efficiently.

rope

like image 31
ekostadinov Avatar answered Oct 22 '22 02:10

ekostadinov