Java带头傀儡结点与不带头傀儡结点的双向单列表创建,附加部分面试题
程序员文章站
2022-08-13 21:26:35
作为一名小白,在学习链表中遇到许许多多的困难,只要相信自己可以,多画图帮助自己思考理解,比别人多努力,多写几遍,总会熟练地掌握链表,没有解决不了的困难,只有不努力的人。带头傀儡结点比较简单,下来先看一下创建代码和测试:创建class ListNode{ public int val; public ListNode next; public ListNode prev; public ListNode (int val){ this.val =...
作为一名小白,在学习链表中遇到许许多多的困难,只要相信自己可以,多画图帮助自己思考理解,比别人多努力,多写几遍,总会熟练地掌握链表,没有解决不了的困难,只有不努力的人。
带头傀儡结点比较简单,下来先看一下创建代码和测试:
创建
class ListNode{
public int val;
public ListNode next;
public ListNode prev;
public ListNode (int val){
this.val = val;
}
}
public class DoubleList {
public ListNode puppetHead;//带傀儡节点的头节点
public ListNode last;
public DoubleList(){
this.puppetHead = new ListNode(-1);
}
//头插法
public void addFirst (int data){
ListNode node = new ListNode(data);
if (this.puppetHead.next == null) {
this.puppetHead.next = node;
node.prev = this.puppetHead;
this.last = node;
return;
}
node.next = this.puppetHead.next;
node.next.prev = node;
this.puppetHead.next = node;
node.prev = this.puppetHead;
}
//尾插法
public void addLast (int data){
ListNode node = new ListNode(data);
if (this.last == null && this.puppetHead.next == null) {
this.puppetHead.next = node;
node.prev = this.puppetHead;
this.last = node;
return;
}
this.last.next = node;
node.prev = this.last;
this.last = node;
}
//任意位置插入
public ListNode searchIndex (int index){
ListNode cur = this.puppetHead.next;
if (index < 0 && index > size()){
return null;
}
while (index < 0){
cur = cur.next;
index--;
}
return cur;
}
public void addIndex (int index, int data){
if (index == 0){
addFirst(data);
return;
}
if (index == size()) {
addLast(data);
return;
}
ListNode node = new ListNode(data);
ListNode cur = searchIndex(index);
if (cur == null){
return;
}
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
//求链表长度
public int size(){
ListNode cur = this.puppetHead.next;
int count = 0;
while (cur != null){
count++;
cur = cur.next;
}
return count;
}
//打印单链表
public void display(){
ListNode cur = this.puppetHead.next;
while (cur != null){
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
//清空单列表
public void clear(){
puppetHead.next = null;
this.last = null;
}
//查找关键字
public boolean contains (int key){
ListNode cur = this.puppetHead.next;
while (cur != null){
ListNode curNext = cur.next;
if (cur.val == key){
return true;
}
cur = curNext;
}
return false;
}
//删除第一次出现的关键字
public void remove (int key){
ListNode cur = this.puppetHead.next;
while (cur != null) {
if (cur.val == key){
if (this.puppetHead.next.val == key){
this.puppetHead.next = cur.next;
cur.next.prev = this.puppetHead;
}else {
cur.prev.next = cur.next;
if (cur.next != null){
cur.next.prev = cur.prev;
}
else {
this.last = this.last.prev;
}
}
return;
}else {
cur = cur.next;
}
}
}
//删除所有关键字
public void removeAll (int key) {
ListNode cur = this.puppetHead.next;
while (cur != null) {
if (cur.val == key) {
if (this.puppetHead.next.val == key) {
this.puppetHead.next = cur.next;
cur.next.prev = this.puppetHead;
} else {
cur.prev.next = cur.next;
if (cur.next != null) {
cur.next.prev = cur.prev;
} else {
this.last = this.last.prev;
}
}
}
cur = cur.next;
}
}
}
测试:
public class TestDemo {
public static void main(String[] args) {
DoubleList doubleList = new DoubleList();
doubleList.addLast(1);
doubleList.addLast(1);
doubleList.addLast(1);
doubleList.addLast(5);
doubleList.addLast(1);
doubleList.addLast(1);
//doubleList.display();
//doubleList.addFirst(9);
//doubleList.display();
// doubleList.remove(1);
doubleList.removeAll(1);
doubleList.display();
}
}
不带头傀儡节点的创建
class ListNode{
public int val;
public ListNode next;//存储对象引用
public ListNode prev;
public ListNode(int val) {
this.val = val;
}
}
public class MyTwoList {
public ListNode head;
public ListNode last;
//头插法
public void addFirst(int val){
ListNode listnode = new ListNode(val);
if (this.head == null){
this.head = listnode;
this.last = listnode;
}
head.prev = listnode;
listnode.next = head;
this.head = listnode;
}
//尾插法
public void addLast(int val){
ListNode listnode = new ListNode(val);
if (this.head == null){
this.head = listnode;
this.last = listnode;
}
last.next = listnode;
listnode.prev = last;
this.last = listnode;
}
//找要插入的位置
public ListNode search(int index){
if (index < 0 || index > size()){
System.out.println("index位置不合法");
}
ListNode cur = this.head;
int count = 0;
while (index != 0){
cur = cur.next;
index--;
}
return cur;
}
//在任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int val){
ListNode listnode = new ListNode(val);
if (index == 0){
addFirst(val);
return;
}
if (index == size()){
addLast(val);
return;
}
ListNode cur = search(index);
if (cur == null){
return;
}
listnode.next = cur;
cur.prev.next =listnode;
listnode.prev = cur.prev;
cur.prev =listnode;
}
//查找是否包含关键字
public boolean contains(int key){
ListNode listnode = this.head;
if (this.head == null){
return false;
}
while (listnode != null){
if (listnode.val == key){
return true;
}
listnode = listnode.next;
}
return false;
}
//删除第一次出现关键字为key的节点
public void remove(int key) {
ListNode listnode = this.head;
while (listnode != null) {
if (listnode.val == key) {
if (this.head.val == key) {
head = head.next;
head.prev = null;
} else if (this.last.val == key) {
last = last.prev;
last.next = null;
} else {
listnode.prev.next = listnode.next;
listnode.next.prev = listnode.prev;
}
return;
}
listnode = listnode.next;
}
}
//删除所有值位key的节点
public void removeAllKey(int key){
ListNode listnode = this.head;
while (listnode != null) {
if (listnode.val == key) {
if (head.val == key) {
if (this.head.next == null){
this.head = null;
return;
}
head = head.next;
head.prev = null;
} else {
listnode.prev.next = listnode.next;
if(listnode.next != null){
listnode.next.prev = listnode.prev;
}else {
this.last = this.last.prev;
}
}
}
listnode = listnode.next;
}
}
//得到单链表长度
public int size(){
int count = 0;
ListNode listnode = this.head;
while (listnode != null){
count++;
listnode = listnode.next;
}
return count;
}
//打印单链表
public void display() {
ListNode listnode = this.head;
while (listnode != null){
System.out.print(listnode.val+" ");
listnode = listnode.next;
}
System.out.println();
}
//清空单链表
public void clear() {
this.head = null;
this.last = null;
}
}
测试:
public class TestDemo {
public static void main(String[] args){
MyTwoList myTwoList = new MyTwoList();
myTwoList.addLast(4);
myTwoList.addLast(5);
myTwoList.addLast(3);
myTwoList.addLast(5);
myTwoList.addLast(5);
myTwoList.display();
myTwoList.remove(4);
myTwoList.display();
myTwoList.removeAllKey(5);
myTwoList.display();
//myTwoList.clear();
System.out.println("asdasdsa");
}
本文地址:https://blog.csdn.net/wah369/article/details/109269314
下一篇: flash怎么画一个简单的火柴人图形?