Форум программистов, компьютерный форум, киберфорум
Наши страницы
Java SE (J2SE)
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/4: Рейтинг темы: голосов - 4, средняя оценка - 5.00
Vlad__i__mir
2 / 2 / 0
Регистрация: 04.01.2017
Сообщений: 307
1

Создать односвязный линейный список и прописать функции добавления и удаления элементов

24.09.2017, 17:47. Просмотров 767. Ответов 18

Доброго времени суток!

Нужно создать одно-связанный линейный список и прописать функции добавления и удаления элементов.

С созданием всё просто, написал:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Item_List{
 
    private int data;
    private Item_List next;
 
    public Item_List (int data){
        this.data=data;
        this.next=null;
    }
 
    public void setData (int data){
        this.data=data;
    }
    public void setNext (Item_List next){
        this.next=next;
    }
    public int getData(){
        return this.data;
    }
    public Item_List getNext(){
        return this.next;
    }
}
Но вот с добавлением и удалением проблема - я не пойму как в java перемещаться по списку?

В С++ была операция "->", которая перемещала ссылочную переменную, которая была того же типа, что и наша структура по переменным списка.

А как в java перемещаться по списку? Есть ли подобная "->" операция?

Объясните пожалуйста!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.09.2017, 17:47
Ответы с готовыми решениями:

Линейный односвязный список
Надо разработать консольное приложение на Java Данные приложения – линейный...

Односвязный Список, метод поиска элементов
Создал односвязный список, добавляет элементы, удаляет. Нужно написать...

Односвязный список, проблема при добавлении элементов
Добрый день. Пишу односвязный список. Узел public class Node<T> { ...

Линейный список: сдвиг элементов на 3 шага вправо
Помогите реализовать метод сдвига элементов на 3 шага вправо с тестовым классом...

Односвязный список с возможность удаления и добавления элементов
Помогите пожалуйста. Нужно сделать программу в Delphi. Условие: Односвязный...

18
evggen0904
3 / 3 / 2
Регистрация: 31.07.2017
Сообщений: 29
25.09.2017, 10:28 2
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Item{
    private int data;
    private Item next;
    
    Item(int data, Item next){
        this.data = data;
        this.next = next;
    }
    
    public Item getNext(){
        return next;
    }
    
    public int getData(){
        return data;
    }
}
 
class MyList{
    private Item root;
    
    public void add(int data){
        Item newItem;
        if (root == null){
            newItem = new Item(data, null);
        }
        else{
            Item current = root;
            while (current.getNext() != null){
                current = current.getNext();
            }
            
            newItem = new Item(data, current);
        }
    }
}
Дальше сам по аналогии сделаешь.
0
Vlad__i__mir
2 / 2 / 0
Регистрация: 04.01.2017
Сообщений: 307
25.09.2017, 13:45  [ТС] 3
Цитата Сообщение от evggen0904 Посмотреть сообщение
current = current.getNext();
- то есть оператор "." автоматически перемещает переменную (current) по списку?
0
evggen0904
3 / 3 / 2
Регистрация: 31.07.2017
Сообщений: 29
25.09.2017, 13:54 4
Точка дает доступ к доступным полям и методам класса. В твоем случае элемент Item содержит ссылку next на другой элемент. И так по цепочке от корневого элемента переходишь ко всем последующим, определяя на какой элемент указывает эта ссылка.
Рекомендую подробнее ознакомиться с азами и понять как работают ссылка в java.
1
Vlad__i__mir
2 / 2 / 0
Регистрация: 04.01.2017
Сообщений: 307
25.09.2017, 14:05  [ТС] 5
evggen0904, спасибо! Я понял механизм.
0
Vlad__i__mir
2 / 2 / 0
Регистрация: 04.01.2017
Сообщений: 307
28.09.2017, 17:45  [ТС] 6
Цитата Сообщение от evggen0904 Посмотреть сообщение
Дальше сам по аналогии сделаешь.
Потребовалось реализовать стек на основании списка. Добавление и удаление с конца написал, но вот с доступом к голове списка не из класса, для вывода например проблемы.

Подскажи пожалуйста как получить доступ к списку из вне.
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public class Dinamik_struct {
 
    public static void main(String [] args)throws IOException{
 
        Stec list=null;
        list.add_end(5);
        list.add_end(4);
        list.add_end(3);
        list.dell_end();
        list.dell_end();
        
        Stec.Item_List list2=list.getHead();
        
        while (list2.getNext()==0){ //НЕ ПОЛУЧАЕТСЯ ПОЛУЧИТЬ ДОСТУП К ГОЛОВЕ СПИСКА
            list.next=
        }
    }
}
 
class Stec {
 
    private Item_List head;
 
    //Добавление в конец
    public void add_end(int data){
 
        Item_List newItem;
        newItem=new Item_List(data,head);
        head.next=newItem;
    }
 
    //Удаление с конца
    public void dell_end(){
        head.next=head.next.next;
    }
    public Item_List getHead(){
        return head.next;
    }
 
    public static class Item_List {
 
        private int data;
        private Item_List next;
 
        public Item_List(int data,Item_List head) {
            this.data = data;
            this.next = head;
        }
        public int getData() {
            return this.data;
        }
        public Item_List getNext() {
            return this.next;
        }
    }
}
Добавлено через 22 минуты
5-ю строка заменена на: Stec list=new Stec();
0
evggen0904
3 / 3 / 2
Регистрация: 31.07.2017
Сообщений: 29
28.09.2017, 20:53 7
Если ты реализовываешь стэк на базе связанного списка, то тебе нужно иметь в твоем списке ссылку на последний элемент(lastElement). И для стэка больше подошел бы двунаправленный список, чтобы можно было от первого к последнему и от последнего к первому элементу продвигаться. При извлечении из стэка(метод pop()), просто берешь и возвращаешь эту ссылку на lastElement. Затем переприсваеваешь предпоследнему элмементу lastElement.

Для получения доступа к первому элементу списка делаешь вот так:

Java
1
2
3
4
5
6
7
class MyList{
    private Item root;
 
    public Item getRoot(){
        return root;
    }
}
Ссылка на рутовый элемент всегда должна храниться в списке.
0
Vlad__i__mir
2 / 2 / 0
Регистрация: 04.01.2017
Сообщений: 307
28.09.2017, 21:28  [ТС] 8
Цитата Сообщение от evggen0904 Посмотреть сообщение
тебе нужно иметь в твоем списке ссылку на последний элемент(lastElement)
А зачем, если я и добавляю и удаляю из головы?
0
korvin_
2202 / 1693 / 323
Регистрация: 28.04.2012
Сообщений: 6,000
29.09.2017, 00:10 9
Цитата Сообщение от evggen0904 Посмотреть сообщение
И для стэка больше подошел бы двунаправленный список, чтобы можно было от первого к последнему и от последнего к первому элементу продвигаться.
Семантика стека — LIFO, никакого «от последнего к первому». Только две (опционально — три) операции: push, pop и (опционально) top. Ну и isEmpty можно добавить, хотя, по-хорошему, ситуации, когда такая проверка нужна, быть не должно.
0
Vlad__i__mir
2 / 2 / 0
Регистрация: 04.01.2017
Сообщений: 307
29.09.2017, 07:28  [ТС] 10
Цитата Сообщение от evggen0904 Посмотреть сообщение
тебе нужно иметь в твоем списке ссылку на последний элемент(lastElement)
Мне это понадобиться для написания очереди.

Объясни пожалуйста как сохранять ссылку на последний элемент списка в стеке?
0
evggen0904
3 / 3 / 2
Регистрация: 31.07.2017
Сообщений: 29
29.09.2017, 08:35 11
Цитата Сообщение от Vlad__i__mir Посмотреть сообщение
Объясни пожалуйста как сохранять ссылку на последний элемент списка в стеке?
Точно так же как с рутовым элементом. Добавил новый - обновил ссылку.
0
Vlad__i__mir
2 / 2 / 0
Регистрация: 04.01.2017
Сообщений: 307
29.09.2017, 09:16  [ТС] 12
Цитата Сообщение от evggen0904 Посмотреть сообщение
Точно так же как с рутовым элементом. Добавил новый - обновил ссылку.
В первом случае я добавлял ссылку на элемент, который добавлял. А здесь получается на тот, который добавил первым и дальше её не обновляем пока не убудет удаление 1-го элемента?

Можно пример кода добавления и обновления её?
0
evggen0904
3 / 3 / 2
Регистрация: 31.07.2017
Сообщений: 29
29.09.2017, 09:22 13
Цитата Сообщение от Vlad__i__mir Посмотреть сообщение
Можно пример кода добавления и обновления её?
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class MyList{
    private Item root;
    private Item last;
 
    public void add(int data){
        Item newItem;
        if (root == null){
            newItem = new Item(data, null);
            root = newItem;
        }
        else{
            Item current = root;
            while (current.getNext() != null){
                current = current.getNext();
            }
 
            newItem = new Item(data, current);
        }
        last = newItem;
    }
}
Забыл в самом первом примере root инициализировать. Тут поправил.
1
Vlad__i__mir
2 / 2 / 0
Регистрация: 04.01.2017
Сообщений: 307
29.09.2017, 19:33  [ТС] 14
Цитата Сообщение от evggen0904 Посмотреть сообщение
Забыл в самом первом примере root инициализировать. Тут поправил.
А как осуществить доступ к методам класса MyList для уже существующего списка, если нам нужен метод, который удаляет дубликаты из уже существующего списка, т.е. он в качестве аргумента принимает объект класса списка?
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
public static Item_List dell_dublekat (Item_List abc){
        Item_List list=abc;
        Item_List list2=abc;
        while (!list.equals(0)) {
 
            while (!list2.data.equals(0) && !list2.next.equals(0)) {
                if(list2.next.data.equals(list.data)) list2.next=list2.next.next;
                else list2=list2.next;
            }
            list=list.next;
        }
        return list2;
    }
Мы же не создаём напрямую объект класса Item, он создаётся объектом класса MyList и хранится внутри него.
0
evggen0904
3 / 3 / 2
Регистрация: 31.07.2017
Сообщений: 29
29.09.2017, 19:49 15
Цитата Сообщение от Vlad__i__mir Посмотреть сообщение
А как осуществить доступ к методам класса MyList для уже существующего списка
Доступ определяют модификаторы доступа(public, private etc).

Если я правильно уловил твою мысль, то тебе нужно использовать геттеры для объектов класса Item.
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Item{
    private int data;
    private Item next;
    
    Item(int data, Item next){
        this.data = data;
        this.next = next;
    }
    
    public Item getNext(){
        return next;
    }
    
    public int getData(){
        return data;
    }
}
Т.е ищешь дубликат так:
Java
1
2
    if (current.getData() == current.getNext().getData()){
    }
Где current - ссылка на текущий элемент в списке.
0
Vlad__i__mir
2 / 2 / 0
Регистрация: 04.01.2017
Сообщений: 307
29.09.2017, 20:08  [ТС] 16
Цитата Сообщение от evggen0904 Посмотреть сообщение
if (current.getData() == current.getNext().getData()){
* * }
Так не пойдёт, т.к. у нас дубликат может идти не сразу за проверяемым, а хоть в самом конце. Поэтому я создаю копиюсписка и сравниваю каждый элемент исходного списка с каждым элементом из копии списка, ну кроме самого себя и если нахожу, то перекидываю через него ссылку.

Я не пойму как вызывать функцию
0
evggen0904
3 / 3 / 2
Регистрация: 31.07.2017
Сообщений: 29
29.09.2017, 20:19 17
Понятно, что дубликат может быть хоть где. А зачем ты создаешь элемент еще один элемент? берешь первый элемент и пробегаеш вксь список в поисках дублей, затем второй и т.д
0
Vlad__i__mir
2 / 2 / 0
Регистрация: 04.01.2017
Сообщений: 307
29.09.2017, 20:27  [ТС] 18
Цитата Сообщение от evggen0904 Посмотреть сообщение
Понятно, что дубликат может быть хоть где. А зачем ты создаешь элемент еще один элемент? берешь первый элемент и пробегаеш вксь список в поисках дублей, затем второй и т.д
А разве когда мы будем сдвигать ссылку на следующий элемент для сравнения с ним:
Java
1
2
3
if (current.getData() == current.getNext().getData()){
* * }
else current=cirrent.next;
у нас значение в current.getData() тоже не сместится на следующий элемент?
0
ArtemFM
247 / 228 / 165
Регистрация: 10.09.2015
Сообщений: 850
05.10.2017, 10:25 19
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
package apavlov.list;
 
import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;
 
/**
 * The class MyLinkedList - enrollment methods for work with link list.
 *
 * @param <E> This describes my type parameter
 * @author Pavlov Artem
 * @since 18.09.2017
 */
public class MyLinkedList<E> implements MyList<E> {
    /**
     * The var - text exception.
     */
    private String msgException = "The element is not found...";
 
    /**
     * The var - count elements to list.
     */
    private int size;
 
    /**
     * The var - link first Node.
     */
    private Node first;
 
    /**
     * The var - link last Node.
     */
    private Node last;
 
    /**
     * The default constructor for class MyLinkedList.
     */
    public MyLinkedList() {
    }
 
    /**
     * The constructor for class MyLinkedList. Add array to list.
     *
     * @param values - array for add;
     */
    public MyLinkedList(E[] values) {
        this.addAll(values);
    }
 
    @Override
    public int size() {
        return size;
    }
 
    @Override
    public boolean isEmpty() {
        return this.size == 0;
    }
 
    @Override
    public void clear() {
        size = 0;
        first = null;
        last = null;
    }
 
    @Override
    public Object[] toArray() {
        Object[] resultArray = new Object[this.size];
        int index = 0;
        for (Node link = first; link != null; link = link.next) {
            resultArray[index++] = link.value;
        }
        return resultArray;
    }
 
    @Override
    public String toString() {
        return Arrays.toString(toArray());
    }
 
    @Override
    public void add(E value) {
        if (this.first == null) {
            first = new Node(null, null, value);
        } else {
            Node prevElement = this.last == null ? this.first : this.last;
            this.last = new Node(prevElement, null, value);
            prevElement.next = this.last;
        }
        this.size++;
    }
 
    /**
     * The private method check index equal range array.
     *
     * @param index - index for check;
     * @return - true - index is range; false - index is not range;
     */
    private boolean checkIndexToRange(int index) {
        return index >= 0 && index < this.size;
    }
 
    /**
     * The method get link Node by index.
     *
     * @param index - index for search;
     * @return - link Node;
     */
    private Node getLinkByIndex(int index) {
        Node result;
        if (this.size >> 1 >= index) {
            result = this.first;
            for (int i = 0; i < index; i++) {
                result = result.next;
            }
        } else {
            result = this.last;
            for (int i = this.size - 1; i > index; i--) {
                result = result.prev;
            }
        }
        return result;
    }
 
    @Override
    public boolean add(int index, E value) {
        boolean result = true;
        if (index == this.size) {
            add(value);
        } else if (checkIndexToRange(index)) {
            Node oldElement = getLinkByIndex(index);
            Node newElement = new Node(oldElement.prev, oldElement, value);
            if (oldElement.prev == null) {
                this.first = newElement;
                this.last = oldElement;
            } else {
                oldElement.prev.next = newElement;
                oldElement.prev = newElement;
            }
            this.size++;
        } else {
            result = false;
        }
        return result;
    }
 
    @Override
    public boolean addAll(E[] values) {
        boolean result = values != null && values.length > 0;
        if (result) {
            for (E value : values) {
                add(value);
            }
        }
        return result;
    }
 
    /**
     * The method return link Node by value.
     *
     * @param value - value;
     * @return - link Node;
     */
    private Node getLinkByValue(E value) {
        Node result = null;
        for (Node element = first; element != null; element = element.next) {
            if (element.value.equals(value)) {
                result = element;
                break;
            }
        }
        return result;
    }
 
    @Override
    public int get(E value) {
        int result = -1;
        int index = 0;
        for (Node node = first; node != null; node = node.next) {
            if (node.value.equals(value)) {
                result = index;
                break;
            }
            index++;
        }
        return result;
    }
 
    @Override
    public E get(int index) {
        E result;
        if (checkIndexToRange(index)) {
            result = getLinkByIndex(index).value;
        } else {
            throw new NoSuchElementException(this.msgException);
        }
        return result;
    }
 
    /**
     * The method delete Node by link.
     *
     * @param node - link Node;
     * @return true - is delete; false - is not delete;
     */
    private boolean deleteByLink(Node node) {
        boolean result = node != null;
        if (result) {
            if (node.next == null && node.prev == null) {
                first = null;
                last = null;
            } else if (node.prev == null) {
                first = node.next;
                first.prev = null;
            } else if (node.next == null) {
                last = node.prev;
                last.next = null;
            } else {
                node.prev.next = node.next;
                node.next.prev = node.prev;
            }
            size--;
        }
        return result;
    }
 
    @Override
    public boolean delete(int index) {
        boolean result = checkIndexToRange(index);
        if (result) {
            result = deleteByLink(getLinkByIndex(index));
        }
        return result;
    }
 
    @Override
    public boolean delete(E value) {
        return deleteByLink(getLinkByValue(value));
    }
 
    @Override
    public E update(int index, E value) {
        E result;
        if (checkIndexToRange(index)) {
            Node temp = getLinkByIndex(index);
            result = temp.value;
            temp.value = value;
        } else {
            throw new NoSuchElementException(this.msgException);
        }
        return result;
    }
 
    @Override
    public Iterator<E> iterator() {
        return new IteratorLinked();
    }
 
    /**
     * The inner class Node - object for save values user and links.
     *
     * @author Pavlov Artem
     * @since 18.09.2017
     */
    private class Node {
        /**
         * The var - link to previous element Node.
         */
        private Node prev;
 
        /**
         * The var - link to next element Node.
         */
        private Node next;
 
        /**
         * The var - value to list.
         */
        private E value;
 
        /**
         * The constructor for class Node.
         *
         * @param prev  - link previous element;
         * @param next  - link next element;
         * @param value - value;
         */
        Node(Node prev, Node next, E value) {
            this.prev = prev;
            this.next = next;
            this.value = value;
        }
    }
 
    /**
     * The inner class IteratorLinked - iterator for class MyLinkedList.
     *
     * @author Pavlov Artem
     * @since 18.09.2017
     */
    private class IteratorLinked implements Iterator<E> {
        /**
         * The var - cursor by linked list.
         */
        private Node cursor = first;
 
        @Override
        public boolean hasNext() {
            return this.cursor != null;
        }
 
        @Override
        public E next() {
            if (!hasNext()) {
                throw new NoSuchElementException(msgException);
            }
            E result = cursor.value;
            this.cursor = this.cursor.next;
            return result;
        }
    }
}
1
05.10.2017, 10:25
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.10.2017, 10:25

Создать очередь, написать функции для добавления/удаления элементов
Добрый. Помогите, пожалуйста. Задание: Разработать функции, позволяющие:...

Создать линейный односвязный список
Создать линейный односвязный список. Из списка удалить отрицательные элементы,...

Создать односвязный линейный список
Доброго времени суток! Помогите пожалуйста с кодом программы: Нужно создать...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
19
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru