如何解决双链接列表实现java stackOverflow Error?
如何解决双链接列表实现java stackOverflow Error?
提问于 2018-08-19 23:56:57
以下是我使用的代码：
public class DLL {
private DLL link;
private DLL prev;
private int n;
private DLL dummy;
private Object x;
public DLL() {
dummy = new DLL(); // this is the line the compiler complains about.
dummy.link = dummy;
dummy.prev = dummy;
n = 0;
}
public DLL getNode(int i){
DLL p = null;
if (i < n /2) {
p = dummy.link;
for (int j = 0; j < i; j++) p = p.link;
} else {
p = dummy;
for (int j = n; j > i; j--)
p = p.prev;
}
return p;
}
public Object get(int i) {
return getNode(i).x;
}
public Object set (int i, Object x) {
DLL u = getNode(i);
Object y = u.x;
u.x = x;
return y;
}
public DLL addBefore(DLL w, Object x) {
DLL u = new DLL();
u.x = x;
u.prev = w.prev;
u.link = w;
u.link.prev = u;
u.prev.link = u;
n++;
return u;
}
public void add(int i, Object x) {
addBefore(getNode(i), x);
}
public void remove(DLL w) {
w.prev.link = w.link;
w.link.prev = w.prev;
n--;
}
public Object remove(int i) {
DLL w = getNode(i);
remove(w);
return w.x;
}
/**
* swaps x w y
* for w x y
* @param w
*/
public DLL swap(DLL w) {
DLL x = w.prev;
DLL y = w.link;
x.prev = w;
w.link = x;
x.link = y;
y.prev = x;
return w;
}
public String toString(){
StringBuffer s = new StringBuffer();
s.append("{");
DLL current = dummy.link;
while (current != null)
{s.append(current.x);
if (current.link != null) s.append(", ");
current = current.link;}
s.append("}");
return s.toString();}
public static void main(String[] args) {
DLL LL = new DLL();
LL.add(1, 4);
LL.add(2, 12);
// System.out.println(LL.toString());
// System.out.println(LL.swap(12);
// System.out.println(LL.toString());
}
}回答 1
Stack Overflow用户
发布于 2018-08-20 09:53:23
下面是实现双链接列表的示例代码：
import java.util.Scanner;
/* Class Node */
class Node
{
protected int data;
protected Node next, prev;
/* Constructor */
public Node()
{
next = null;
prev = null;
data = 0;
}
/* Constructor */
public Node(int d, Node n, Node p)
{
data = d;
next = n;
prev = p;
}
/* Function to set link to next node */
public void setLinkNext(Node n)
{
next = n;
}
/* Function to set link to previous node */
public void setLinkPrev(Node p)
{
prev = p;
}
/* Funtion to get link to next node */
public Node getLinkNext()
{
return next;
}
/* Function to get link to previous node */
public Node getLinkPrev()
{
return prev;
}
/* Function to set data to node */
public void setData(int d)
{
data = d;
}
/* Function to get data from node */
public int getData()
{
return data;
}
}
/* Class linkedList */
class linkedList
{
protected Node start;
protected Node end ;
public int size;
/* Constructor */
public linkedList()
{
start = null;
end = null;
size = 0;
}
/* Function to check if list is empty */
public boolean isEmpty()
{
return start == null;
}
/* Function to get size of list */
public int getSize()
{
return size;
}
/* Function to insert element at begining */
public void insertAtStart(int val)
{
Node nptr = new Node(val, null, null);
if(start == null)
{
start = nptr;
end = start;
}
else
{
start.setLinkPrev(nptr);
nptr.setLinkNext(start);
start = nptr;
}
size++;
}
/* Function to insert element at end */
public void insertAtEnd(int val)
{
Node nptr = new Node(val, null, null);
if(start == null)
{
start = nptr;
end = start;
}
else
{
nptr.setLinkPrev(end);
end.setLinkNext(nptr);
end = nptr;
}
size++;
}
/* Function to insert element at position */
public void insertAtPos(int val , int pos)
{
Node nptr = new Node(val, null, null);
if (pos == 1)
{
insertAtStart(val);
return;
}
Node ptr = start;
for (int i = 2; i <= size; i++)
{
if (i == pos)
{
Node tmp = ptr.getLinkNext();
ptr.setLinkNext(nptr);
nptr.setLinkPrev(ptr);
nptr.setLinkNext(tmp);
tmp.setLinkPrev(nptr);
}
ptr = ptr.getLinkNext();
}
size++ ;
}
/* Function to delete node at position */
public void deleteAtPos(int pos)
{
if (pos == 1)
{
if (size == 1)
{
start = null;
end = null;
size = 0;
return;
}
start = start.getLinkNext();
start.setLinkPrev(null);
size--;
return ;
}
if (pos == size)
{
end = end.getLinkPrev();
end.setLinkNext(null);
size-- ;
}
Node ptr = start.getLinkNext();
for (int i = 2; i <= size; i++)
{
if (i == pos)
{
Node p = ptr.getLinkPrev();
Node n = ptr.getLinkNext();
p.setLinkNext(n);
n.setLinkPrev(p);
size-- ;
return;
}
ptr = ptr.getLinkNext();
}
}
/* Function to display status of list */
public void display()
{
System.out.print("\nDoubly Linked List = ");
if (size == 0)
{
System.out.print("empty\n");
return;
}
if (start.getLinkNext() == null)
{
System.out.println(start.getData() );
return;
}
Node ptr = start;
System.out.print(start.getData()+ " <-> ");
ptr = start.getLinkNext();
while (ptr.getLinkNext() != null)
{
System.out.print(ptr.getData()+ " <-> ");
ptr = ptr.getLinkNext();
}
System.out.print(ptr.getData()+ "\n");
}
}
/* Class DoublyLinkedList */
public class DoublyLinkedList
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of linkedList */
linkedList list = new linkedList();
System.out.println("Doubly Linked List Test\n");
char ch;
/* Perform list operations */
do
{
System.out.println("\nDoubly Linked List Operations\n");
System.out.println("1. insert at begining");
System.out.println("2. insert at end");
System.out.println("3. insert at position");
System.out.println("4. delete at position");
System.out.println("5. check empty");
System.out.println("6. get size");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
list.insertAtStart( scan.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to insert");
list.insertAtEnd( scan.nextInt() );
break;
case 3 :
System.out.println("Enter integer element to insert");
int num = scan.nextInt() ;
System.out.println("Enter position");
int pos = scan.nextInt() ;
if (pos < 1 || pos > list.getSize() )
System.out.println("Invalid position\n");
else
list.insertAtPos(num, pos);
break;
case 4 :
System.out.println("Enter position");
int p = scan.nextInt() ;
if (p < 1 || p > list.getSize() )
System.out.println("Invalid position\n");
else
list.deleteAtPos(p);
break;
case 5 :
System.out.println("Empty status = "+ list.isEmpty());
break;
case 6 :
System.out.println("Size = "+ list.getSize() +" \n");
break;
default :
System.out.println("Wrong Entry \n ");
break;
}
/* Display List */
list.display();
System.out.println("\nDo you want to continue (Type y or n) \n");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/-100002261
复制相关文章
相似问题