「java包双向链表」java双链表结构
今天给各位分享java包双向链表的知识，其中也会对java双链表结构进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
本文目录一览：
- 1、在Java中如何实现双向链表?
- 2、java双向链表
- 3、java 什么是单向链表 和 双向链表 ？
- 4、java中 双向链表是什么意思啊，是用来干啥的啊，求大神解答？谢谢
- 5、Java 双向链表
在Java中如何实现双向链表?
双向链表：就是有双向指针，即双向的链域。
链结点的结构：
┌────┬────┬────────┐
│ data │ next │ previous │
└────┴────┴────────┘
双向链表不必是双端链表(持有对最后一个链结点的引用)，双端链表插入时是双向的。
有两条链：一条从头到尾，一条从尾到头，删除遍历时也是双向的。
/**
* 双向链表
*/
public class DoublyLinkedListt {
private Linkt head; //首结点
private Linkt rear; //尾部指针
public DoublyLinkedList() { }
public T peekHead() {
if (head != null) {
return head.data;
}
return null;
}
public boolean isEmpty() {
return head == null;
}
public void insertFirst(T data) {// 插入 到 链头
Linkt newLink = new Linkt(data);
if (isEmpty()) {//为空时，第1次插入的新结点为尾结点
rear = newLink;
} else {
head.previous = newLink; //旧头结点的上结点等于新结点
}
newLink.next = head; //新结点的下结点旧头结点
head = newLink; //赋值后，头结点的下结点是旧头结点，上结点null
}
public void insertLast(T data) {//在链尾 插入
Linkt newLink = new Linkt(data);
if (isEmpty()) {
head = newLink;
} else {
rear.next = newLink;
}
newLink.previous = rear;
rear = newLink; //赋值后，尾结点的上结点是旧尾结点，下结点null
}
public T deleteHead() {//删除 链头
if (isEmpty()) return null;
Linkt temp = head;
head = head.next; //变更首结点，为下一结点
if (head != null) {
head.previous = null;
} else {
rear = null;
}
return temp.data;
}
public T deleteRear() {//删除 链尾
if (isEmpty()) return null;
Linkt temp = rear;
rear = rear.previous; //变更尾结点，为上一结点
if (rear != null) {
rear.next = null;
} else {
head = null;
}
return temp.data;
}
public T find(T t) {//从头到尾find
if (isEmpty()) {
return null;
}
Linkt find = head;
while (find != null) {
if (!find.data.equals(t)) {
find = find.next;
} else {
break;
}
}
if (find == null) {
return null;
}
return find.data;
}
public T delete(T t) {
if (isEmpty()) {
return null;
}
Linkt current = head;
while (!current.data.equals(t)) {
current = current.next;
if (current == null) {
return null;
}
}
if (current == head) {
head = head.next;
if (head != null) {
head.previous = null;
}
} else if (current == rear) {
rear = rear.previous;
if (rear != null) {
rear.next = null;
}
} else {
//中间的非两端的结点，要移除current
current.next.previous = current.previous;
current.previous.next = current.next;
}
return current.data;
}
public boolean insertAfter(T key, T data) {//插入在key之后, key不存在return false
if (isEmpty()) {
return false;
}
Linkt current = head;
while (!current.data.equals(key)) {
current = current.next;
if (current == null) {
return false;
}
}
Linkt newLink = new Linkt(data);
if (current == rear) {
rear = newLink;
} else {
newLink.next = current.next;
current.next.previous = newLink;
}
current.next = newLink;
newLink.previous = current;
return true;
}
public void displayList4Head() {//从头开始遍历
System.out.println("List (first--last):");
Linkt current = head;
while (current != null) {
current.displayLink();
current = current.next;
}
}
public void displayList4Rear() {//从尾开始遍历
System.out.println("List (last--first):");
Linkt current = rear;
while (current != null) {
current.displayLink();
current = current.previous;
}
}
class Linkt {//链结点
T data; //数据域
Linkt next; //后继指针，结点 链域
Linkt previous; //前驱指针，结点 链域
Link(T data) {
this.data = data;
}
void displayLink() {
System.out.println("the data is " + data.toString());
}
}
public static void main(String[] args) {
DoublyLinkedListinteger list = new DoublyLinkedListinteger();
list.insertLast(1);
list.insertFirst(2);
list.insertLast(3);
list.insertFirst(4);
list.insertLast(5);
list.displayList4Head();
Integer deleteHead = list.deleteHead();
System.out.println("deleteHead:" + deleteHead);
list.displayList4Head();
Integer deleteRear = list.deleteRear();
System.out.println("deleteRear:" + deleteRear);
list.displayList4Rear();
System.out.println("find:" + list.find(6));
System.out.println("find:" + list.find(3));
System.out.println("delete find:" + list.delete(6));
System.out.println("delete find:" + list.delete(1));
list.displayList4Head();
System.out.println("----在指定key后插入----");
list.insertAfter(2, 8);
list.insertAfter(2, 9);
list.insertAfter(9, 10);
list.displayList4Head();
}
}
java双向链表
public boolean putAfter(Object obj,DoublyListNode node)//有可能找不到obj,所以我返回boolean
{
DoublyListNode current = head;
while(head.obj!=obj){
current = current.next;
if(current==null)
return false;
}
if(current==tail){
node.next = null;
tail = node;
}else{
node.next = current.next;
current.next.previous = node;
}
node.previous = current;
current.next =node;
return true;
}
public DoublyListNode removeafter(Object obj){//返回了选中的节点
DoublyListNode current = head;
while(current.obj!=obj)
{
current = current.next;
if(current == null)
return null;
}
if(current==head)
head = current.next;
else
current.previous.next = current.next;
if(current == tail)
tail = current.previous;
else
current.next.previous = current.previous;
return current;
}
java 什么是单向链表 和 双向链表 ？
链表是类似一种数据结构的东西，就是分别存放有地址以及数据单项链表一般是上一个存放地址的地方存放下一个节点的地址，而双向的就是有两个存放地址的地方，分别存上一个以及下一个的地址。大概是这样子
java中 双向链表是什么意思啊，是用来干啥的啊，求大神解答？谢谢
采用双向循环链表作为数据结构
1 新元素的下一个指向header
2 新元素的上一个指向header的上一个
3 新元素的上一个的下一个指向新元素
4 新元素的下一个的上一个指向新元素
一般LinkedList是采用双向循环链表，无需扩容，添加元素添加到最后即可
Java 双向链表
import java.util.*;
public class DoublyLinkedList {
//overview: a list that is doublylinked
private ListNode firstNode;
private ListNode lastNode;
//constructors:
public DoublyLinkedList(){
//EFFECTS: initialize this to be empty
firstNode = null;
lastNode = null;
}
//methods:
public synchronized void insertAtFront(Object o){
//EFFECTS: add o to the front of this
//MODIFIES: this
if(isEmpty()){
firstNode = lastNode = firstNode.nextNode = firstNode.prevNode = lastNode.nextNode = lastNode.prevNode = new ListNode(o);
}
else{
firstNode = new ListNode(o , firstNode , lastNode);
lastNode.nextNode = firstNode;
}
}
public synchronized void insertAtBack(Object o){
//EFFECTS: add o to the back of this
//MODIFIES: this
if(isEmpty()){
firstNode = lastNode = firstNode.nextNode = firstNode.prevNode = lastNode.nextNode = lastNode.prevNode = new ListNode(o);
}
else{
lastNode = lastNode.nextNode = new ListNode(o , lastNode , firstNode);
firstNode.prevNode = lastNode;
}
}
public synchronized Object removeFromFront() throws EmptyListException{
//EFFECTS: remove the first node of this and return the node
//MODIFIES: this
Object o = null;
if(isEmpty()){
throw new EmptyListException();
}
else{
o = firstNode.data;
if(firstNode == lastNode){
firstNode = lastNode = null;
}
else{
firstNode = firstNode.nextNode;
firstNode.prevNode = lastNode;
firstNode.nextNode = firstNode;
}
}
return o;
}
public synchronized Object removeFromBack() throws EmptyListException{
//EFFECTS: remove the last node of this and return the node
//MODIFIES: this
Object o = null;
if(isEmpty()){
throw new EmptyListException();
}
else{
o = firstNode.data;
if(firstNode == lastNode){
firstNode = lastNode = null;
}
else{
lastNode = lastNode.prevNode;
lastNode.nextNode = firstNode;
firstNode.prevNode = lastNode;
}
}
return o;
}
public synchronized Set LocalMaximum(){
//EFFECTS: 返回一个Set，其中每个元素为位置信息，在该位置处的链表元素值为极大值
//极大值是指该元素不小于其直接前驱及直接后继元素
ListNode current = firstNode;
SetInteger a = null ;
int n = 0;
while(current.nextNode != firstNode){
if(Integer.parseInt(current.data.toString()) = Integer.parseInt(current.prevNode.data.toString())
Integer.parseInt(current.data.toString()) = Integer.parseInt(current.nextNode.data.toString()))
a.add(new Integer(n));
n++;
}
return a;
}
public Iterator iterator(int direction) throws Exception{
//EFFECTS: if direction is 0 return a generator that will produce all elements of this from the first node to the last one
//else if direction is 0 return a generator that will produce all elements of this from the last node to the first one
//REQUIRES: this must not be modified while the generator is in use
if(direction == 0){
return new fl(this);
}
else if(direction == 1){
return new lf(this);
}
else{
throw new Exception("Enter the right direction!");
}
}
//inner class
private static class fl implements Iterator{
//overview: from first to last
private ListNode current;
private DoublyLinkedList y;
//constructors:
public fl(DoublyLinkedList x){
//EFFECTS: initialize this
y = x;
current = y.firstNode;
}
//methods:
public boolean hasNext(){
//EFFECTS: return true if there are more elements else return false
if(current == y.lastNode)
return false;
else
return true;
}
public Object next() throws NoSuchElementException{
//EFFECTS: If there are more results to yield, returns the next result and modifies the state of this to record the yield.
// Otherwise throws NoSuchElementException
if(current == y.lastNode)
throw new NoSuchElementException("DoublyLinkedList.iterator");
else{
current = current.nextNode;
return current;
}
}
public void remove() throws UnsupportedOperationException{
throw new UnsupportedOperationException("DoublyLinkedList.iterator");
}
//end methods
//end constructors
}//end class
private static class lf implements Iterator{
//overview: from last to first
private ListNode current;
private DoublyLinkedList y;
//constructors:
public lf(DoublyLinkedList x){
//EFFECTS: initialize this
y = x;
current = y.lastNode;
}
//methods:
public boolean hasNext(){
//EFFECTS: return true if there are more elements else return false
if(current == y.firstNode)
return false;
else
return true;
}
public Object next() throws NoSuchElementException{
//EFFECTS: If there are more results to yield, returns the next result and modifies the state of this to record the yield.
// Otherwise throws NoSuchElementException
if(current == y.firstNode)
throw new NoSuchElementException("DoublyLinkedList.iterator");
else{
current = current.prevNode;
return current;
}
}
public void remove() throws UnsupportedOperationException{
throw new UnsupportedOperationException("DoublyLinkedList.iterator");
}
//end methods
// end constructors
}//end class
public synchronized boolean isEmpty(){
//EFFECTS: if this is not empty retutn true else return false
return firstNode == null;
}
//end methods
//end constructors
}//end class
class ListNode{
//overview: ListNode is the node of a list
Object data;
ListNode nextNode;
ListNode prevNode;
//constructors:
public ListNode(Object o){
//EFFECTS: initialize this to be a node like(o , null)
this( o , null , null);
}
public ListNode(Object o , ListNode node1 , ListNode node2){
//EFFECTS: initialize this to be a node like(node1 , o , node2)
data = o ;
nextNode = node1;
prevNode = node2;
}
//methods:
Object getObject(){
//EFFECTS: return the object of this
return data;
}
ListNode getNext(){
//EFFECTS: return the next node of this
return nextNode;
}
ListNode getPrev(){
//EFFECTS: return the prev node of this
return prevNode;
}
//end methods
//end constructors
}//end class
class EmptyListException extends RuntimeException {
//constructors:
public EmptyListException(){
//EFFECTS: initialize an EmptyListException
super( "The list is empty" );
}
} // end class
曾经自己编过,好像...贴给你了..
java包双向链表的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于java双链表结构、java包双向链表的信息别忘了在本站进行查找喔。