Java 从头开始创建 LinkedList 类
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4066729/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Creating a LinkedList class from scratch
提问by Snowman
We were given an assignment to create a LinkedList from scratch, and there are absolutely no readings given to guide us on this migrane-causing task. Also everything online seems to just use Java's built in LinkedList methods and stuff. Anyway, linked lists make perfect sense when using Java's default stuff, but creating it from scratch makes no sense whatsoever. Lets say I have
我们被分配了从头开始创建 LinkedList 的任务，并且绝对没有任何阅读材料可以指导我们完成这项导致偏头痛的任务。此外，网上的一切似乎都只使用 Java 内置的 LinkedList 方法和东西。无论如何，链表在使用 Java 的默认内容时非常有意义，但是从头开始创建它没有任何意义。可以说我有
public class LinkedList {
private LinkedList next;
private final String word;
// constructor
public LinkedList(String word, LinkedList next) {
this.word = word;
this.next = next;
}
And thus magically we have a linked list. What is going on? How have I created a linked list like this? How does this work? I'm supposed to write an append method that adds a the given String wordparameter to the end of thislinkedlist. I tried looking at the addLast built in method for built in java linkedlist class, but it's no help to me, as I really dont understand whats going on. Anyone care to help me out :)
因此神奇的是我们有一个链表。到底是怎么回事？我是如何创建这样的链表的？这是如何运作的？我应该编写一个 append 方法，将给定的String word参数添加到this链表的末尾。我尝试查看内置 java 链接列表类的 addLast 内置方法，但这对我没有帮助，因为我真的不明白发生了什么。任何人都愿意帮助我:)
采纳答案by Laurence Gonsalves
If you're actually building a real system, then yes, you'd typically just use the stuff in the standard library if what you need is available there. That said, don't think of this as a pointless exercise. It's good to understand how things work, and understanding linked lists is an important step towards understanding more complex data structures, many of which don't exist in the standard libraries.
如果您实际上正在构建一个真正的系统，那么是的，如果您需要的东西在那里可用，您通常只会使用标准库中的东西。也就是说，不要认为这是一个毫无意义的练习。理解事物是如何工作的很好，理解链表是理解更复杂数据结构的重要一步，其中许多数据结构在标准库中并不存在。
There are some differences between the way you're creating a linked list and the way the Java collections API does it. The Collections API is trying to adhere to a more complicated interface. The Collections API linked list is also a doubly linked list, while you're building a singly linked list. What you're doing is more appropriate for a class assignment.
创建链接列表的方式与 Java 集合 API 的创建方式之间存在一些差异。Collections API 试图遵循更复杂的接口。Collections API 链表也是一个双向链表，而您正在构建一个单链表。你所做的更适合课堂作业。
With your LinkedListclass, an instance will always be a list of at least one element. With this kind of setup you'd use nullfor when you need an empty list.
对于您的LinkedList类，实例将始终是至少一个元素的列表。使用这种设置，您null可以在需要空列表时使用。
Think of nextas being "the rest of the list". In fact, many similar implementations use the name "tail" instead of "next".
将其next视为“列表的其余部分”。事实上，许多类似的实现使用名称“tail”而不是“next”。
Here's a diagram of a LinkedListcontaining 3 elements:
这是一个LinkedList包含 3 个元素的图：
Note that it's a LinkedListobject pointing to a word ("Hello") and a list of 2 elements. The list of 2 elements has a word ("Stack") and a list of 1 element. That list of 1 element has a word ("Overflow") and an empty list (null). So you can treat nextas just another list that happens to be one element shorter.
请注意，它是一个LinkedList指向单词（“Hello”）和 2 个元素的列表的对象。2 个元素的列表有一个词（“堆栈”）和一个 1 个元素的列表。1 个元素的列表有一个词（“溢出”）和一个空列表（null）。因此，您可以将其next视为恰好是一个元素更短的另一个列表。
You may want to add another constructor that just takes a String, and sets next to null. This would be for creating a 1-element list.
您可能想要添加另一个只接受一个字符串的构造函数，并在 旁边设置null。这将用于创建 1 元素列表。
To append, you check if nextis null. If it is, create a new one element list and set nextto that.
要追加，请检查是否next为null。如果是，则创建一个新的单元素列表并设置next为该列表。
next = new LinkedList(word);
If next isn't null, then append to nextinstead.
如果 next 不是null，则next改为附加到。
next.append(word);
This is the recursive approach, which is the least amount of code. You can turn that into an iterative solution which would be more efficient in Java*, and wouldn't risk a stack overflow with very long lists, but I'm guessing that level of complexity isn't needed for your assignment.
这是递归方法，代码量最少。您可以将其转换为在 Java * 中效率更高的迭代解决方案，并且不会冒很长列表的堆栈溢出风险，但我猜您的分配不需要这种复杂程度。
* Some languages have tail call elimination, which is an optimization that lets the language implementation convert "tail calls" (a call to another function as the very last step before returning) into (effectively) a "goto". This makes such code completely avoid using the stack, which makes it safer (you can't overflow the stack if you don't use the stack) and typically more efficient. Scheme is probably the most well known example of a language with this feature.
* 某些语言具有尾调用消除功能，这是一种优化，可让语言实现将“尾调用”（对另一个函数的调用作为返回前的最后一步）转换为（有效地）“转到”。这使得此类代码完全避免使用堆栈，从而使其更安全（如果不使用堆栈，则不会溢出堆栈）并且通常更高效。Scheme 可能是最广为人知的具有此功能的语言示例。
回答by Kevin Stricker
How have I created a linkedlist like this. How does this work?This is all a linked list is. An item with a link to the next item in the list. As long as you keep a reference to the item at the beginning of the list, you can traverse the whole thing using each subsequent reference to the next value.
我是如何创建这样的链表的。这是如何运作的？这就是链表的全部内容。带有指向列表中下一个项目的链接的项目。只要您在列表的开头保留对项目的引用，就可以使用对下一个值的每个后续引用来遍历整个事物。
To append, all you need to do is find the end of the list, and make the next item the value you want appended, so if this has non-null next, you would have to call append on the next item until you find the end of the list.
要追加，您需要做的就是找到列表的末尾，并使下一项成为您想要追加的值，因此，如果 next 非空，则必须在下一项上调用 append 直到找到列表的结尾。
this.next.Append(word);
回答by OmnipotentEntity
Sure, a Linked List is a bit confusing for programming n00bs, pretty much the temptation is to look at it as Russian Dolls, because that's what it seems like, a LinkedList Object in a LinkedList Object. But that's a touch difficult to visualize, instead look at it like a computer.
当然，链表对于 n00bs 编程有点令人困惑，几乎是将它视为俄罗斯娃娃的诱惑，因为这就是它看起来的样子，LinkedList 对象中的 LinkedList 对象。但这很难想象，而是像电脑一样看待它。
LinkedList = Data + Next Member
LinkedList = 数据 + 下一个成员
Where it's the last member of the list if next is NULL
如果 next 为 NULL，则它是列表的最后一个成员
So a 5 member LinkedList would be:
所以一个 5 成员 LinkedList 将是：
LinkedList(Data1, LinkedList(Data2, LinkedList(Data3, LinkedList(Data4, LinkedList(Data5, NULL)))))
LinkedList(Data1, LinkedList(Data2, LinkedList(Data3, LinkedList(Data4, LinkedList(Data5, NULL)))))
But you can think of it as simply:
但你可以简单地认为：
Data1 -> Data2 -> Data3 -> Data4 -> Data5 -> NULL
数据 1 -> 数据 2 -> 数据 3 -> 数据 4 -> 数据 5 -> NULL
So, how do we find the end of this? Well, we know that the NULL is the end so:
那么，我们如何找到这个结局呢？好吧，我们知道 NULL 是结尾，所以：
public void append(LinkedList myNextNode) {
LinkedList current = this; //Make a variable to store a pointer to this LinkedList
while (current.next != NULL) { //While we're not at the last node of the LinkedList
current = current.next; //Go further down the rabbit hole.
}
current.next = myNextNode; //Now we're at the end, so simply replace the NULL with another Linked List!
return; //and we're done!
}
This is very simple code of course, and it willinfinitely loop if you feed it a circularly linked list! But that's the basics.
这当然是非常简单的代码，如果你给它一个循环链表，它就会无限循环！但这是最基本的。
回答by Amir Afghani
What you have coded is not a LinkedList, at least not one that I recognize. For this assignment, you want to create two classes:
您编写的代码不是LinkedList，至少不是我认识的。对于此作业，您要创建两个类：
LinkNode
LinkedList
A LinkNodehas one member field for the data it contains, and a LinkNodereference to the next LinkNodein the LinkedList. Yes, it's a self referential data structure. A LinkedListjust has a special LinkNodereference that refers to the first item in the list.
阿LinkNode具有用于它包含的数据中的一个成员字段，以及LinkNode到下一个基准LinkNode在LinkedList。是的，它是一种自引用数据结构。ALinkedList只是有一个特殊的LinkNode引用，它指的是列表中的第一项。
When you add an item in the LinkedList, you traverse all the LinkNode'suntil you reach the last one. This LinkNode'snext should be null. You then construct a new LinkNodehere, set it's value, and add it to the LinkedList.
当您在 中添加一个项目时LinkedList，您会遍历所有 ，LinkNode's直到到达最后一个。这LinkNode's下一个应该是空的。然后LinkNode在这里构造一个新的，设置它的值，并将它添加到LinkedList.
public class LinkNode {
String data;
LinkNode next;
public LinkNode(String item) {
data = item;
}
}
public class LinkedList {
LinkNode head;
public LinkedList(String item) {
head = new LinkNode(item);
}
public void add(String item) {
//pseudo code: while next isn't null, walk the list
//once you reach the end, create a new LinkNode and add the item to it. Then
//set the last LinkNode's next to this new LinkNode
}
}
回答by Stephen C
Hint 1: read the description of linked lists at http://en.wikipedia.org/wiki/Linked_list
提示 1：在http://en.wikipedia.org/wiki/Linked_list阅读链表的描述
Hint 2: the Java implementation of LinkedList is a doubly linked list. Yours is a singly linked list. The algorithms don't directly apply.
提示 2：LinkedList 的 Java 实现是双向链表。你的是一个单向链表。这些算法不直接适用。
Also:
还：
... but creating [a linked list class] from scratch makes no sense whatsoever.
...但是从头开始创建 [一个链表类] 没有任何意义。
It depends on what the required outcome of the work is. If the goal is to produce code that meets certain functional / non-functional requirements, then you are right. If the realgoal is for you to learnhow to program / design APIs / implement non-trivial data structures, then the utility of the final product is almost entirely irrelevant.
这取决于工作所需的结果是什么。如果目标是生成满足某些功能/非功能要求的代码，那么您是对的。如果真正的目标是让您学习如何编程/设计 API/实现非平凡的数据结构，那么最终产品的实用性几乎完全无关紧要。
And thus magically we have a linked list
因此神奇地我们有一个链表
What you actually have there is a open data type, that could be used to build a (sort of) list. But that is not what your teacher wants. And it certainly would not be considered to be a usefullist abstraction. A useful abstraction would include:
您实际拥有的是一种开放数据类型，可用于构建（某种）列表。但这不是你老师想要的。它当然不会被认为是一个有用的列表抽象。一个有用的抽象包括：
methods to do the things that programmers don't want to have to repeat over and over again, and
an abstraction layer that stops programmers "breaking" the list; e.g. by accidentally creating a cycle, or accidentally stitching a sublist in two lists to create an inverted tree.
方法来做程序员不想一遍又一遍地重复的事情，以及
阻止程序员“破坏”列表的抽象层；例如，意外地创建了一个循环，或者意外地将一个子列表拼接在两个列表中以创建一个倒置的树。
回答by Evan Plaice
How about a fully functional implementation of a non-recursive Linked List?
非递归链表的全功能实现怎么样？
I created this for my Algorithms I class as a stepping stone to gain a better understanding before moving onto writing a doubly-linked queue class for an assignment.
我为我的 Algorithms I 类创建了这个作为垫脚石，以便在继续为作业编写双向链接队列类之前获得更好的理解。
Here's the code:
这是代码：
import java.util.Iterator;
import java.util.NoSuchElementException;
public class LinkedList<T> implements Iterable<T> {
private Node first;
private Node last;
private int N;
public LinkedList() {
first = null;
last = null;
N = 0;
}
public void add(T item) {
if (item == null) { throw new NullPointerException("The first argument for addLast() is null."); }
if (!isEmpty()) {
Node prev = last;
last = new Node(item, null);
prev.next = last;
}
else {
last = new Node(item, null);
first = last;
}
N++;
}
public boolean remove(T item) {
if (isEmpty()) { throw new IllegalStateException("Cannot remove() from and empty list."); }
boolean result = false;
Node prev = first;
Node curr = first;
while (curr.next != null || curr == last) {
if (curr.data.equals(item)) {
// remove the last remaining element
if (N == 1) { first = null; last = null; }
// remove first element
else if (curr.equals(first)) { first = first.next; }
// remove last element
else if (curr.equals(last)) { last = prev; last.next = null; }
// remove element
else { prev.next = curr.next; }
N--;
result = true;
break;
}
prev = curr;
curr = prev.next;
}
return result;
}
public int size() {
return N;
}
public boolean isEmpty() {
return N == 0;
}
private class Node {
private T data;
private Node next;
public Node(T data, Node next) {
this.data = data;
this.next = next;
}
}
public Iterator<T> iterator() { return new LinkedListIterator(); }
private class LinkedListIterator implements Iterator<T> {
private Node current = first;
public T next() {
if (!hasNext()) { throw new NoSuchElementException(); }
T item = current.data;
current = current.next;
return item;
}
public boolean hasNext() { return current != null; }
public void remove() { throw new UnsupportedOperationException(); }
}
@Override public String toString() {
StringBuilder s = new StringBuilder();
for (T item : this)
s.append(item + " ");
return s.toString();
}
public static void main(String[] args) {
LinkedList<String> list = new LinkedList<>();
while(!StdIn.isEmpty()) {
String input = StdIn.readString();
if (input.equals("print")) { StdOut.println(list.toString()); continue; }
if (input.charAt(0) == ('+')) { list.add(input.substring(1)); continue; }
if (input.charAt(0) == ('-')) { list.remove(input.substring(1)); continue; }
break;
}
}
}
Note: It's a pretty basic implementation of a singly-linked-list. The 'T' type is a generic type placeholder. Basically, this linked list should work with any type that inherits from Object. If you use it for primitive types be sure to use the nullable class equivalents (ex 'Integer' for the 'int' type). The 'last' variable isn't really necessary except that it shortens insertions to O(1) time. Removals are slow since they run in O(N) time but it allows you to remove the first occurrence of a value in the list.
注意：这是一个非常基本的单链表实现。'T' 类型是泛型类型占位符。基本上，这个链表应该适用于任何继承自 Object 的类型。如果将它用于原始类型，请确保使用可空类等价物（例如，“int”类型的“整数”）。'last' 变量并不是真正必要的，只是它将插入时间缩短到 O(1) 时间。删除很慢，因为它们在 O(N) 时间内运行，但它允许您删除列表中第一次出现的值。
If you want you could also look into implementing:
如果您愿意，您还可以考虑实施：
- addFirst() - add a new item to the beginning of the LinkedList
- removeFirst() - remove the first item from the LinkedList
- removeLast() - remove the last item from the LinkedList
- addAll() - add a list/array of items to the LinkedList
- removeAll() - remove a list/array of items from the LinkedList
- contains() - check to see if the LinkedList contains an item
- contains() - clear all items in the LinkedList
- addFirst() - 在 LinkedList 的开头添加一个新项目
- removeFirst() - 从 LinkedList 中删除第一项
- removeLast() - 从 LinkedList 中删除最后一项
- addAll() - 将项目列表/数组添加到 LinkedList
- removeAll() - 从 LinkedList 中删除项目列表/数组
- contains() - 检查 LinkedList 是否包含一个项目
- contains() - 清除 LinkedList 中的所有项目
Honestly, it only takes a few lines of code to make this a doubly-linked list. The main difference between this and a doubly-linked-list is that the Node instances of a doubly-linked list require an additional reference that points to the previous element in the list.
老实说，只需要几行代码就可以使它成为一个双向链表。这与双向链表的主要区别在于双向链表的 Node 实例需要一个指向列表中前一个元素的附加引用。
The benefit of this over a recursive implementation is that it's faster and you don't have to worry about flooding the stack when you traverse large lists.
与递归实现相比，这样做的好处是速度更快，而且您不必担心在遍历大型列表时会淹没堆栈。
There are 3 commands to test this in the debugger/console:
在调试器/控制台中有 3 个命令可以对此进行测试：
- Prefixing a value by a '+' will add it to the list.
- Prefixing with a '-' will remove the first occurrence from the list.
- Typing 'print' will print out the list with the values separated by spaces.
- 以“+”为前缀的值会将其添加到列表中。
- 以“-”为前缀将从列表中删除第一次出现。
- 键入 'print' 将打印出列表，其中的值以空格分隔。
If you have never seen the internals of how one of these works I suggest you step through the following in the debugger:
如果您从未见过其中之一如何工作的内部结构，我建议您在调试器中逐步执行以下操作：
- add() - tacks a new node onto the end or initializes the first/last values if the list is empty
- remove() - walks the list from the start-to-end. If it finds a match it removes that item and connects the broken links between the previous and next links in the chain. Special exceptions are added when there is no previous or next link.
- toString() - uses the foreach iterator to simply walk the list chain from beginning-to-end.
- add() - 如果列表为空，则在末尾添加一个新节点或初始化第一个/最后一个值
- remove() - 从头到尾遍历列表。如果找到匹配项，它将删除该项目并连接链中前一个和下一个链接之间的断开链接。当没有上一个或下一个链接时，会添加特殊例外。
- toString() - 使用 foreach 迭代器从头到尾简单地遍历列表链。
While there are better and more efficient approaches for lists like array-lists, understanding how the application traverses via references/pointers is integral to understanding how many higher-level data structures work.
虽然对于数组列表等列表有更好、更有效的方法，但了解应用程序如何通过引用/指针遍历对于了解有多少更高级别的数据结构工作是不可或缺的。
回答by Eadhunath
class Node
{
int data;
Node link;
public Node()
{
data=0;
link=null;
}
Node ptr,start,temp;
void create()throws IOException
{
int n;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter first data");
this.data=Integer.parseInt(br.readLine());
ptr=this;
start=ptr;
char ins ='y';
do
{
System.out.println("Wanna Insert another node???");
ins=(char)br.read();
br.read();
if(ins=='y')
{
temp=new Node();
System.out.println("Enter next data");
temp.data=Integer.parseInt(br.readLine());
temp.link=null;
ptr.link=temp;
temp=null;
ptr=ptr.link;
}
}while(ins=='y');
}
public static void main(String args[])throws IOException
{
Node first= new Node();
first.create();
}
}
回答by d.danailov
Please read this article: How To Implement a LinkedList Class From Scratch In Java
请阅读这篇文章：如何在 Java 中从头开始实现 LinkedList 类
package com.crunchify.tutorials;
/**
* @author Crunchify.com
*/
public class CrunchifyLinkedListTest {
public static void main(String[] args) {
CrunchifyLinkedList lList = new CrunchifyLinkedList();
// add elements to LinkedList
lList.add("1");
lList.add("2");
lList.add("3");
lList.add("4");
lList.add("5");
/*
* Please note that primitive values can not be added into LinkedList
* directly. They must be converted to their corresponding wrapper
* class.
*/
System.out.println("lList - print linkedlist: " + lList);
System.out.println("lList.size() - print linkedlist size: " + lList.size());
System.out.println("lList.get(3) - get 3rd element: " + lList.get(3));
System.out.println("lList.remove(2) - remove 2nd element: " + lList.remove(2));
System.out.println("lList.get(3) - get 3rd element: " + lList.get(3));
System.out.println("lList.size() - print linkedlist size: " + lList.size());
System.out.println("lList - print linkedlist: " + lList);
}
}
class CrunchifyLinkedList {
// reference to the head node.
private Node head;
private int listCount;
// LinkedList constructor
public CrunchifyLinkedList() {
// this is an empty list, so the reference to the head node
// is set to a new node with no data
head = new Node(null);
listCount = 0;
}
public void add(Object data)
// appends the specified element to the end of this list.
{
Node crunchifyTemp = new Node(data);
Node crunchifyCurrent = head;
// starting at the head node, crawl to the end of the list
while (crunchifyCurrent.getNext() != null) {
crunchifyCurrent = crunchifyCurrent.getNext();
}
// the last node's "next" reference set to our new node
crunchifyCurrent.setNext(crunchifyTemp);
listCount++;// increment the number of elements variable
}
public void add(Object data, int index)
// inserts the specified element at the specified position in this list
{
Node crunchifyTemp = new Node(data);
Node crunchifyCurrent = head;
// crawl to the requested index or the last element in the list,
// whichever comes first
for (int i = 1; i < index && crunchifyCurrent.getNext() != null; i++) {
crunchifyCurrent = crunchifyCurrent.getNext();
}
// set the new node's next-node reference to this node's next-node
// reference
crunchifyTemp.setNext(crunchifyCurrent.getNext());
// now set this node's next-node reference to the new node
crunchifyCurrent.setNext(crunchifyTemp);
listCount++;// increment the number of elements variable
}
public Object get(int index)
// returns the element at the specified position in this list.
{
// index must be 1 or higher
if (index <= 0)
return null;
Node crunchifyCurrent = head.getNext();
for (int i = 1; i < index; i++) {
if (crunchifyCurrent.getNext() == null)
return null;
crunchifyCurrent = crunchifyCurrent.getNext();
}
return crunchifyCurrent.getData();
}
public boolean remove(int index)
// removes the element at the specified position in this list.
{
// if the index is out of range, exit
if (index < 1 || index > size())
return false;
Node crunchifyCurrent = head;
for (int i = 1; i < index; i++) {
if (crunchifyCurrent.getNext() == null)
return false;
crunchifyCurrent = crunchifyCurrent.getNext();
}
crunchifyCurrent.setNext(crunchifyCurrent.getNext().getNext());
listCount--; // decrement the number of elements variable
return true;
}
public int size()
// returns the number of elements in this list.
{
return listCount;
}
public String toString() {
Node crunchifyCurrent = head.getNext();
String output = "";
while (crunchifyCurrent != null) {
output += "[" + crunchifyCurrent.getData().toString() + "]";
crunchifyCurrent = crunchifyCurrent.getNext();
}
return output;
}
private class Node {
// reference to the next node in the chain,
// or null if there isn't one.
Node next;
// data carried by this node.
// could be of any type you need.
Object data;
// Node constructor
public Node(Object dataValue) {
next = null;
data = dataValue;
}
// another Node constructor if we want to
// specify the node to point to.
public Node(Object dataValue, Node nextValue) {
next = nextValue;
data = dataValue;
}
// these methods should be self-explanatory
public Object getData() {
return data;
}
public void setData(Object dataValue) {
data = dataValue;
}
public Node getNext() {
return next;
}
public void setNext(Node nextValue) {
next = nextValue;
}
}
}
Output
输出
lList - print linkedlist: [1][2][3][4][5]
lList.size() - print linkedlist size: 5
lList.get(3) - get 3rd element: 3
lList.remove(2) - remove 2nd element: true
lList.get(3) - get 3rd element: 4
lList.size() - print linkedlist size: 4
lList - print linkedlist: [1][3][4][5]
回答by Shiv Buyya
Linked list to demonstrate Insert Front, Delete Front, Insert Rear and Delete Rear operations in Java:
用于演示 Java 中插入前部、删除前部、插入后部和删除后部操作的链表：
import java.io.DataInputStream;
import java.io.IOException;
public class LinkedListTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
Node root = null;
DataInputStream reader = new DataInputStream(System.in);
int op = 0;
while(op != 6){
try {
System.out.println("Enter Option:\n1:Insert Front 2:Delete Front 3:Insert Rear 4:Delete Rear 5:Display List 6:Exit");
//op = reader.nextInt();
op = Integer.parseInt(reader.readLine());
switch (op) {
case 1:
System.out.println("Enter Value: ");
int val = Integer.parseInt(reader.readLine());
root = insertNodeFront(val,root);
display(root);
break;
case 2:
root=removeNodeFront(root);
display(root);
break;
case 3:
System.out.println("Enter Value: ");
val = Integer.parseInt(reader.readLine());
root = insertNodeRear(val,root);
display(root);
break;
case 4:
root=removeNodeRear(root);
display(root);
break;
case 5:
display(root);
break;
default:
System.out.println("Invalid Option");
break;
}
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
System.out.println("Exited!!!");
try {
reader.close();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
static Node insertNodeFront(int value, Node root){
Node temp = new Node(value);
if(root==null){
return temp; // as root or first
}
else
{
temp.next = root;
return temp;
}
}
static Node removeNodeFront(Node root){
if(root==null){
System.out.println("List is Empty");
return null;
}
if(root.next==null){
return null; // remove root itself
}
else
{
root=root.next;// make next node as root
return root;
}
}
static Node insertNodeRear(int value, Node root){
Node temp = new Node(value);
Node cur = root;
if(root==null){
return temp; // as root or first
}
else
{
while(cur.next!=null)
{
cur = cur.next;
}
cur.next = temp;
return root;
}
}
static Node removeNodeRear(Node root){
if(root==null){
System.out.println("List is Empty");
return null;
}
Node cur = root;
Node prev = null;
if(root.next==null){
return null; // remove root itself
}
else
{
while(cur.next!=null)
{
prev = cur;
cur = cur.next;
}
prev.next=null;// remove last node
return root;
}
}
static void display(Node root){
System.out.println("Current List:");
if(root==null){
System.out.println("List is Empty");
return;
}
while (root!=null){
System.out.print(root.val+"->");
root=root.next;
}
System.out.println();
}
static class Node{
int val;
Node next;
public Node(int value) {
// TODO Auto-generated constructor stub
val = value;
next = null;
}
}
}
回答by Vpn_talent
Linked List Program with following functionalities
具有以下功能的链表程序
1 Insert At Start
2 Insert At End
3 Insert At any Position
4 Delete At any Position
5 Display
6 Get Size
7 Empty Status
8 Replace data at given postion
9 Search Element by position
10 Delete a Node by Given Data
11 Search Element Iteratively
12 Search Element Recursively
package com.elegant.ds.linkedlist.practice;
import java.util.Scanner;
class Node {
Node link = null;
int data = 0;
public Node() {
link = null;
data = 0;
}
public Node(int data, Node link) {
this.data = data;
this.link = null;
}
public Node getLink() {
return link;
}
public void setLink(Node link) {
this.link = link;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
}
class SinglyLinkedListImpl {
Node start = null;
Node end = null;
int size = 0;
public SinglyLinkedListImpl() {
start = null;
end = null;
size = 0;
}
public void insertAtStart(int data) {
Node nptr = new Node(data, null);
if (start == null) {
start = nptr;
end = start;
} else {
nptr.setLink(start);
start = nptr;
}
size++;
}
public void insertAtEnd(int data) {
Node nptr = new Node(data, null);
if (start == null) {
start = nptr;
end = nptr;
} else {
end.setLink(nptr);
end = nptr;
}
size++;
}
public void insertAtPosition(int position, int data) {
Node nptr = new Node(data, null);
Node ptr = start;
position = position - 1;
for (int i = 1; i < size; i++) {
if (i == position) {
Node temp = ptr.getLink();
ptr.setLink(nptr);
nptr.setLink(temp);
break;
}
ptr = ptr.getLink();
}
size++;
}
public void repleaceDataAtPosition(int position, int data) {
if (start == null) {
System.out.println("Empty!");
return;
}
Node ptr = start;
for (int i = 1; i < size; i++) {
if (i == position) {
ptr.setData(data);
}
ptr = ptr.getLink();
}
}
public void deleteAtPosition(int position) {
if (start == null) {
System.out.println("Empty!");
return;
}
if (position == size) {
Node startPtr = start;
Node endPtr = start;
while (startPtr != null) {
endPtr = startPtr;
startPtr = startPtr.getLink();
}
end = endPtr;
end.setLink(null);
size--;
return;
}
Node ptr = start;
position = position - 1;
for (int i = 1; i < size; i++) {
if (i == position) {
Node temp = ptr.getLink();
temp = temp.getLink();
ptr.setLink(temp);
break;
}
ptr = ptr.getLink();
}
size--;
}
public void deleteNodeByGivenData(int data) {
if (start == null) {
System.out.println("Empty!");
return;
}
if (start.getData() == data && start.getLink() == null) {
start = null;
end = null;
size--;
return;
}
if (start.getData() == data && start.getLink() != null) {
start = start.getLink();
size--;
return;
}
if (end.getData() == data) {
Node startPtr = start;
Node endPtr = start;
startPtr = startPtr.getLink();
while (startPtr.getLink() != null) {
endPtr = startPtr;
startPtr = startPtr.getLink();
}
end = endPtr;
end.setLink(null);
size--;
return;
}
Node startPtr = start;
Node prevLink = startPtr;
startPtr = startPtr.getLink();
while (startPtr.getData() != data && startPtr.getLink() != null) {
prevLink = startPtr;
startPtr = startPtr.getLink();
}
if (startPtr.getData() == data) {
Node temp = prevLink.getLink();
temp = temp.getLink();
prevLink.setLink(temp);
size--;
return;
}
System.out.println(data + " not found!");
}
public void disply() {
if (start == null) {
System.out.println("Empty!");
return;
}
if (start.getLink() == null) {
System.out.println(start.getData());
return;
}
Node ptr = start;
System.out.print(ptr.getData() + "->");
ptr = start.getLink();
while (ptr.getLink() != null) {
System.out.print(ptr.getData() + "->");
ptr = ptr.getLink();
}
System.out.println(ptr.getData() + "\n");
}
public void searchElementByPosition(int position) {
if (position == 1) {
System.out.println("Element at " + position + " is : " + start.getData());
return;
}
if (position == size) {
System.out.println("Element at " + position + " is : " + end.getData());
return;
}
Node ptr = start;
for (int i = 1; i < size; i++) {
if (i == position) {
System.out.println("Element at " + position + " is : " + ptr.getData());
break;
}
ptr = ptr.getLink();
}
}
public void searchElementIteratively(int data) {
if (isEmpty()) {
System.out.println("Empty!");
return;
}
if (start.getData() == data) {
System.out.println(data + " found at " + 1 + " position");
return;
}
if (start.getLink() != null && end.getData() == data) {
System.out.println(data + " found at " + size + " position");
return;
}
Node startPtr = start;
int position = 0;
while (startPtr.getLink() != null) {
++position;
if (startPtr.getData() == data) {
break;
}
startPtr = startPtr.getLink();
}
if (startPtr.getData() == data) {
System.out.println(data + " found at " + position);
return;
}
System.out.println(data + " No found!");
}
public void searchElementRecursively(Node start, int data, int count) {
if (isEmpty()) {
System.out.println("Empty!");
return;
}
if (start.getData() == data) {
System.out.println(data + " found at " + (++count));
return;
}
if (start.getLink() == null) {
System.out.println(data + " not found!");
return;
}
searchElementRecursively(start.getLink(), data, ++count);
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return start == null;
}
}
public class SinglyLinkedList {
@SuppressWarnings("resource")
public static void main(String[] args) {
SinglyLinkedListImpl listImpl = new SinglyLinkedListImpl();
System.out.println("Singly Linked list : ");
boolean yes = true;
do {
System.out.println("1 Insert At Start :");
System.out.println("2 Insert At End :");
System.out.println("3 Insert At any Position :");
System.out.println("4 Delete At any Position :");
System.out.println("5 Display :");
System.out.println("6 Get Size");
System.out.println("7 Empty Status");
System.out.println("8 Replace data at given postion");
System.out.println("9 Search Element by position ");
System.out.println("10 Delete a Node by Given Data");
System.out.println("11 Search Element Iteratively");
System.out.println("12 Search Element Recursively");
System.out.println("13 Exit :");
Scanner scanner = new Scanner(System.in);
int choice = scanner.nextInt();
switch (choice) {
case 1:
listImpl.insertAtStart(scanner.nextInt());
break;
case 2:
listImpl.insertAtEnd(scanner.nextInt());
break;
case 3:
int position = scanner.nextInt();
if (position <= 1 || position > listImpl.getSize()) {
System.out.println("invalid position!");
} else {
listImpl.insertAtPosition(position, scanner.nextInt());
}
break;
case 4:
int deletePosition = scanner.nextInt();
if (deletePosition <= 1 || deletePosition > listImpl.getSize()) {
System.out.println("invalid position!");
} else {
listImpl.deleteAtPosition(deletePosition);
}
break;
case 5:
listImpl.disply();
break;
case 6:
System.out.println(listImpl.getSize());
break;
case 7:
System.out.println(listImpl.isEmpty());
break;
case 8:
int replacePosition = scanner.nextInt();
if (replacePosition < 1 || replacePosition > listImpl.getSize()) {
System.out.println("Invalid position!");
} else {
listImpl.repleaceDataAtPosition(replacePosition, scanner.nextInt());
}
break;
case 9:
int searchPosition = scanner.nextInt();
if (searchPosition < 1 || searchPosition > listImpl.getSize()) {
System.out.println("Invalid position!");
} else {
listImpl.searchElementByPosition(searchPosition);
}
break;
case 10:
listImpl.deleteNodeByGivenData(scanner.nextInt());
break;
case 11:
listImpl.searchElementIteratively(scanner.nextInt());
break;
case 12:
listImpl.searchElementRecursively(listImpl.start, scanner.nextInt(), 0);
break;
default:
System.out.println("invalid choice");
break;
}
} while (yes);
}
}
It will help you in linked list.
它将在链表中帮助您。
